LeetCode5 最长回文子串 Longest Palindromic Substring

LeetCode5 最长回文子串 Longest Palindromic Substring

题目描述

题目地址：https://leetcode-cn.com/problems/longest-palindromic-substring/

题目难度：中等

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例

示例1： 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 示例2： 输入: "cbbd" 输出: "bb"

分析

看到这道题目，首先我会想到的方法是动态规划，虽然说大致思路是有了，但我在执行过程中部分细节处理不当导致得出结果出错，主要问题就是回文串长度的奇偶两种情况我合到一块进行的分析，导致最后找不到一个合适的变量比较两种类型的大小，或者说是这两个值会互相受影响。于是我把奇偶分开来分析，最后分别取出最大然后比较大小。

方法1：

public String longestPalindrome(String s) { int n = s.length(); int start = 0; int end = 1; int max = 0; Boolean[][] state = new Boolean[n][n]; if (n <= 1 ) { return s; } for (int i = 0; i < n ; i++) { for (int j = 0; j <= Math.min(i, n - i - 1); j++) { if (i + j + 2 < n && s.charAt(i - j) == s.charAt(i + 2 + j)) { state[i][j] = (j > 0 && state[i][j - 1]) || j == 0; if (state[i][j] && 2 * j + 3 >= max && 2 * j + 3 < n - 1) { start = i - j; end = i + j + 3; max = 2 * j + 3; } } else if (i + j + 1 < n && s.charAt(i - j) == s.charAt(i + 1 + j)) { state[i][j] = (j > 0 && state[i][j - 1]) || j == 0; if (state[i][j] && 2 * j + 2 > max && 2 * j + 2 <= n) { start = i - j; end = i + j + 2; max = 2 * j + 2; } }else { state[i][j] = false; } } } return s.substring(start, end); }

这种方法在临界值总会有内容出错，像aaaabaaa和aaabaaaa，往左边调整第一种出错，往右边调整第二种出错，于是就调整思路，将两种类型分开计算。

方法2：动态规划

思路：如果我们已经知道 “bab” 是回文，那么很明显，“ababa” 一定是回文，因为它的左首字母和右尾字母是相同的。

public String longestPalindrome1(String s) { int n = s.length(); int start = 0; int end = 1; int max = 0; if (n <= 1 ) { return s; } for (int i = 0; i < n - 1; i++) { int left = i; int right1 = i; int right2 = i + 1; int len1 = getLongest(left, right1, s); int len2 = getLongest(left, right2, s); if (len1 > len2 && len1 > max) { max =len1; start = left - len1 / 2; end = right1 + len1 / 2 + 1; } else if (len2 > len1 && len2 > max){ max = len2; start = left - len2 / 2 + 1; end = right2 + len2 / 2; } } return s.substring(start, end); } private int getLongest(int left, int right, String s) { int len = s.length(); Boolean[] state = new Boolean[len]; int i = 0; while (left >= 0 && right <= len - 1) { state[i] = i > 0 && s.charAt(left) == s.charAt(right) && state[i - 1] == true || (i ==0 && s.charAt(left) == s.charAt(right)); if (!state[i]) { return right - left - 1; } else if (state[i] && (left == 0 || right == len - 1)) { return right - left + 1; } left--; right++; i++; } return right - left - 1; }

耗时：134ms 击败了31.77%的提交记录，实在是不乐观。

复杂度分析 O(n^2)

方法3：中心扩展

思路：

事实上，只需使用恒定的空间，我们就可以在O(n^2) 的时间内解决这个问题。 我们观察到回文中心的两侧互为镜像。因此，回文可以从它的中心展开，并且只有2n−1 个这样的中心。 为什么会是2n−1 个，而不是 n 个中心？原因在于所含字母数为偶数的回文的中心可以处于两字母之间。

public String longestPalindrome2(String s) { if (s == null || s.length() < 1) return ""; int start = 0, end = 0; for (int i = 0; i < s.length(); i++) { //按两种情况求取最大长度 int len1 = expandAroundCenter(s, i, i); int len2 = expandAroundCenter(s, i, i + 1); int len = Math.max(len1, len2); if (len > end - start) { start = i - (len - 1) / 2; end = i + len / 2; } } return s.substring(start, end + 1); } private int expandAroundCenter(String s, int left, int right) { int L = left, R = right; while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) { L--; R++; } return R - L - 1; }

耗时：20ms

这种方法主要是看的官方解答，是我目前发现的最好的思路，这个解法是先取出所有可能的中心，然后向两个方向扩展，直到取到不同值，不仅思路简单，处理起来也很方便，值得借鉴。

相似题目

最短回文串

回文排列

回文对

最长回文子序列

回文子串

总结

虽然说一开始就想到了合适的方法，但还是在一些细节处理上导致结果与预期出现偏差，所以下手之前要把问题考虑清楚，不能说是先把大部分考虑到，一些特殊的样例是在调试中慢慢发现，这样更加消耗时间。