题目要求
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
题目翻译：给定一个字符串，找到最长的回文字串，假定字符串长度最大为1000，并存在唯一的最大回文子串。
题目分析一
假设s(j+1,k-1)是一个回文串，且s[j]==s[k]，可证，s(j,k)也一定是一个回文串。由此启发，我们可以记录之前的结果作为启发信息，以利于后面的判断和搜索。该算法的复杂度为O(n^2)。
package com.linsiyue;
public class Solution {
public String longestPalindrome(String s) {
int n = s.length();
int lo = 0,maxLen = 0;
// 声明一个boolean型二维数值，s(j,k)为回文串则boolean[i][j]=true
// 其中 i<=j
boolean[][] dp = new boolean[n][n];
for (int i = n-1; i >= 0; i--) {
for (int j = i; j < n; j++) {
// 关键点是j-i<3这个边界条件的加入，搜索问题要定义明确边界条件
// 当字符串长度为1或i=0时，dp[i+1][j-1]会出现数组越界的错误
// 当s.charAt(i)==s.charAt(j) && j-i<3 时，是回文串，如aba,aa
dp[i][j] = s.charAt(i)==s.charAt(j) && (j-i<3 ||dp[i+1][j-1]);
if (dp[i][j] && j-i+1>maxLen){
lo = i;
maxLen = j-i+1;
}
}
}
return s.substring(lo,lo+maxLen);
}
}
题目分析二
长度为偶数的回文串，有如下性质：中间的两个字符s[i]==s[i+1],且s[i-1]==s[i+2]，依次向两边对称递推，直到碰到回文串边界。长度为奇数的回文串，最中间的数的两边的数相等，即s[i-1]==s[i+1]，隐含着一个重要条件，s[i]==s[i]，有了该隐含条件，递推模式即如偶数。
因此奇偶数情况可以抽象为一个模型：由中间向两边，依次比较轴对称的两个字符，直到两个字符不相等，即可获得该回文串的起始地址及长度。
函数extendPalindrome(String s, int j, int k)即是该模型的实现。
package com.linsiyue;
public class Solution {
private int lo, maxLen;
public String longestPalindrome(String s) {
int len = s.length();
if (len<2)
return s;
for (int i = 0; i < len-1; i++) {
// 奇数情况
extendPalindrome(s,i,i);
// 偶数情况
extendPalindrome(s,i,i+1);
}
return s.substring(lo, lo+maxLen);
}
public void extendPalindrome(String s, int j, int k) {
while (j>=0 && k<s.length() && s.charAt(j)==s.charAt(k)){
j--;
k++;
}
// 跳出while循环时，回文串的开头和结尾游标分别被-1和+1
// 因此计算长度的补回：len=(k-1)-(j+1)+1=k-j-1
if(maxLen < k-j-1){
lo = j+1;
maxLen = k-j-1;
}
}
}
