问题:
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
输入: "babad"
输出: "bab"
注意: "aba"也是一个有效答案。
思路:暴破
package xyz.quxiao.play.lab.leetcode; /** * 给定字符串,查找最长回文 "babad" -> "bab"或"aba"; "cbbd" -> "bb" * * @author 作者 :quxiao 创建时间:2017/11/14 20:17 */public class Problem5 { public static void main(String[] args) { run("babad"); run("cbbd"); } public static void run(String s) { System.out.println(s + ": " + longestPalindrome(s)); } // 思路:暴破,i从0到最后,以i为奇数中心和偶数左边分别查找 public static String longestPalindrome(String s) { int total = s.length(); String ret = ""; for (int i = 0; i < total; i++) { String odd = findPalindromeOdd(s, i); String even = findPalindromeEven(s, i); if (odd.length() > ret.length()) { ret = odd; } if (even != null && even.length() > ret.length()) { ret = even; } } return ret; } // 以idx为中心 public static String findPalindromeOdd(String s, int idx) { int size = s.length(); int start = idx - 1; int end = idx + 1; while (start >= 0 && end < size && s.charAt(start) == s.charAt(end)) { --start; ++end; } return s.substring(++start, end); } // 以idx和idx+1为中心 public static String findPalindromeEven(String s, int idx) { int size = s.length(); int comp = idx + 1; if (comp < size) { if (s.charAt(idx) == s.charAt(comp)) { int start = idx - 1; int end = idx + 2; while (start >= 0 && end < size && s.charAt(start) == s.charAt(end)) { start--; end++; } return s.substring(start + 1, end); } else { return null; } } else { return null; } } }
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于