1，中心扩散法
中心扩散法也很好理解，我们遍历字符串的每一个字符，然后以当前字符为中心往两边扩散，查找最长的回文子串，下面随便举个例子，看一下
图片中我们是以每一个字符为中心，往两边扩散，来求最长的回文子串。但忽略了一个问题，回文串的长度不一定都是奇数，也可能是偶数，比如字符串"abba"，如果使用上面的方式判断肯定是不对的。
我们来思考这样一个问题，如果是单个字符，我们可以认为他是回文子串，如果是多个字符，并且他们都是相同的，那么他们也是回文串。
所以对于上面的问题，我们以当前字符为中心往两边扩散的时候，先要判断和他挨着的有没有相同的字符，如果有，则直接跳过，来看下代码
public int getLongestPalindrome(String A, int n) {
//边界条件判断
if (n < 2)
return A.length();
//maxLen表示最长回文串的长度
int maxLen = 0;
for (int i = 0; i < n; ) {
//如果剩余子串长度小于目前查找到的最长回文子串的长度，直接终止循环
// （因为即使他是回文子串，也不是最长的，所以直接终止循环，不再判断）
if (n - i <= maxLen / 2)
break;
int left = i;
int right = i;
while (right < n - 1 && A.charAt(right + 1) == A.charAt(right))
++right; //过滤掉重复的
//下次在判断的时候从重复的下一个字符开始判断
i = right + 1;
//然后往两边判断，找出回文子串的长度
while (right < n - 1 && left > 0 && A.charAt(right + 1) == A.charAt(left - 1)) {
++right;
--left;
}
//保留最长的
if (right - left + 1 > maxLen) {
maxLen = right - left + 1;
}
}
//截取回文子串
return maxLen;
}
2，暴力求解
暴力求解是最容易想到的，要截取字符串的所有子串，然后再判断这些子串中哪些是回文的，最后返回回文子串中最长的即可。
这里我们可以使用两个变量，一个记录最长回文子串开始的位置，一个记录最长回文子串的长度，最后再截取。代码如下
public int getLongestPalindrome(String A, int n) {
//边界条件判断
if (n < 2)
return A.length();
int maxLen = 0;
for (int i = 0; i < n - 1; i++) {
for (int j = i; j < n; j++) {
//截取所有子串，然后在逐个判断是否是回文的
if (isPalindrome(A, i, j)) {
if (maxLen < j - i + 1) {
maxLen = j - i + 1;
}
}
}
}
return maxLen;
}
//判断是否是回文串
private boolean isPalindrome(String s, int start, int end) {
while (start < end) {
if (s.charAt(start++) != s.charAt(end--))
return false;
}
return true;
}
实际上面代码其实还可以优化一下，在截取的时候，如果截取的长度小于等于目前查找到的最长回文子串，我们可以直接跳过，不需要再判断了，因为即使他是回文子串，也不可能是最长的。
public int getLongestPalindrome(String A, int n) {
//边界条件判断
if (n < 2)
return A.length();
int maxLen = 0;
for (int i = 0; i < n - 1; i++) {
for (int j = i; j < n; j++) {
//截取所有子串，然后在逐个判断是否是回文的
if (isPalindrome(A, i, j)) {
if (maxLen < j - i + 1) {
maxLen = j - i + 1;
}
}
}
}
return maxLen;
}
//判断是否是回文串
private boolean isPalindrome(String s, int start, int end) {
while (start < end) {
if (s.charAt(start++) != s.charAt(end--))
return false;
}
return true;
}
3，动态规划
定义二维数组dp[length][length]，如果dp[left][right]为true，则表示字符串从left到right是回文子串，如果dp[left][right]为false，则表示字符串从left到right不是回文子串。
如果dp[left+1][right-1]为true，我们判断s.charAt(left)和s.charAt(right)是否相等，如果相等，那么dp[left][right]肯定也是回文子串，否则dp[left][right]一定不是回文子串。
所以我们可以找出递推公式
dp[left][right]=s.charAt(left)==s.charAt(right)&&dp[left+1][right-1]
有了递推公式，还要确定边界条件：
如果s.charAt(left)！=s.charAt(right)，那么字符串从left到right是不可能构成子串的，直接跳过即可。
如果s.charAt(left)==s.charAt(right)，字符串从left到right能不能构成回文子串还需要进一步判断
- 如果
left==right，也就是说只有一个字符，我们认为他是回文子串。即dp[left][right]=true（left==right） - 如果
right-left<=2，类似于"aa"，或者"aba"，我们认为他是回文子串。即dp[left][right]=true（right-left<=2） - 如果
right-left>2，我们只需要判断dp[left+1][right-1]是否是回文子串，才能确定dp[left][right]是否为true还是false。即dp[left][right]=dp[left+1][right-1]
有了递推公式和边界条件，代码就很容易写了，来看下
public int getLongestPalindrome(String A, int n) {
//边界条件判断
if (n < 2)
return A.length();
//start表示最长回文串开始的位置，
//maxLen表示最长回文串的长度
int maxLen = 1;
boolean[][] dp = new boolean[n][n];
for (int right = 1; right < n; right++) {
for (int left = 0; left <= right; left++) {
//如果两种字符不相同，肯定不能构成回文子串
if (A.charAt(left) != A.charAt(right))
continue;
//下面是s.charAt(left)和s.charAt(right)两个
//字符相同情况下的判断
//如果只有一个字符，肯定是回文子串
if (right == left) {
dp[left][right] = true;
} else if (right - left <= 2) {
//类似于"aa"和"aba"，也是回文子串
dp[left][right] = true;
} else {
//类似于"a******a"，要判断他是否是回文子串，只需要
//判断"******"是否是回文子串即可
dp[left][right] = dp[left + 1][right - 1];
}
//如果字符串从left到right是回文子串，只需要保存最长的即可
if (dp[left][right] && right - left + 1 > maxLen) {
maxLen = right - left + 1;
}
}
}
//最长的回文子串
return maxLen;
}
京公网安备 11010502036488号