给你一个字符串 s,找到 s 中最长的回文子串。leetcode链接
第一种就是遍历每个位置,从当前位置开始向两边检查最大回文串
这个方法需要注意的是:由于回文串的长度可能为奇数或者偶数,所以检查的时候,要考虑两种情况;
find(i, i)
i
和下一个位置i+1
开始检查,find(i, i+1)
代码
class Solution { public String longestPalindrome(String s) { if (s == null || s.length() <= 0) return s; int maxLen = 0; int start = 0; for (int i = 0; i < s.length(); i++) { int len1 = find(s.toCharArray(), i, i); // 长度为奇数 int len2 = find(s.toCharArray(), i, i + 1); // 长度为偶数 int len = Math.max(len1, len2); if (len > maxLen) { maxLen = len; // 0 1 2 i = 1, len = 3, start = 1 - (2/2) = 0 // 0 1 2 3 i = 1, len = 4, start = 1 - (3/2) = 0 start = i - (len - 1) / 2; } } // substring(a,b) 是左闭右开 return s.substring(start, start + maxLen); } // 从当前位置寻找最长回文串 private int find(char[] cs, int left, int right) { int len = cs.length; while (left >= 0 && right < len && cs[left] == cs[right]) { left--; right++; } return right - left - 1; } }
i
,就在区间\([0, i]\)内两边往中间逼近,得到当前区间内的最大回文串。i
和 j
时是否为回文串,如果是,那只要 \(cs[i - 1] == cs[j + 1]\),那么因为内层为回文串且左右边界字符相等代码
class Solution { public String longestPalindrome(String s) { if (s == null || s.length() < 2) { return s; } char[] cs = s.toCharArray(); int maxLen = 1; int start = 0; boolean[][] dp = new boolean[cs.length][cs.length]; for (int j = 0; j < cs.length; j++) { for (int i = 0; i < j; i++) { // 三个字符以内,或者内部为回文串 if (cs[i] == cs[j] && (j - i <= 2 || dp[i+1][j-1])) { dp[i][j] = true; if (j - i + 1 > maxLen) { maxLen = j - i + 1; start = i; } } } } return s.substring(start, start + maxLen); } }