目录
一、暴力解法：
二、中心解法：
三、动态规划：
一、暴力解法：
最直接的办法就是枚举所有长度大于1的子串并从中选出长度最长的。
class Solution {
public String longestPalindrome(String s) {
char[] str=s.toCharArray();
int len=s.length();
if(len < 2){
return s;
}
int maxlen=1,begin=0;
for(int i=0;i maxlen){
maxlen = j-i+1;
begin = i;
}
}
}
return s.substring(begin, begin + maxlen);
}
public boolean isPalindromic(char[] str, int left, int right){ //判断是否为回文子串
while(left
暴力的时间复杂度是O(N^3) ，时间开销大
二、中心解法：
暴力枚举每种情况找回文子串时间复杂度太高，从左右边界开始检查回文子串效率太低，如果到最后发现中间不是回文子串，就非常的浪费。此时可以反过来思考，回文子串是通过中间向两边扩散的，如果中间的是回文子串，这么就继续查找左右两边。
我们枚举每一种所有可能是中心子串的位置，并从对应的子串开始不断地向两边扩展。如果两边的字母相同，我们就可以继续扩展；如果两边的字母不同，我们就可以停止扩展，因为在这之后的子串都不能是回文串了。
class Solution {
public String longestPalindrome(String s) {
if (s == null || s.length() < 1) {
return "";
}
int start = 0, maxlen=1;
for (int i = 0; i < s.length(); i++) {
int len1 = expandAroundCenter(s, i, i); // 以i为中心
int len2 = expandAroundCenter(s, i, i + 1); // 以i和i+1为中心
int len = Math.max(len1, len2);
if (len > maxlen) {
start = i - (len - 1) / 2;
maxlen = len;
}
}
return s.substring(start, start + maxlen );
}
public int expandAroundCenter(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
--left;
++right;
}
return right - left - 1;
}
}
三、动态规划：
要判断一个长度大于1的子串str [ i, i+1, ... j-1, j ] 是否为回文子串，需要判断 str[i] 是否等于str[j] &&【i+1】~【j-1】是否为回文子串。
借助辅助数组dp[n][n]来存储，dp[row][col]表示第row个元素到第col个元素是否为回文子串。因为j>i，因此在整个过程中只需用到dp的主对角线的上半部分。
遍历过程中需要注意的问题：
1、递推顺序问题：由于i+1>i, j-1
2、边界问题：什么时候dp[i][j] 的值不需要考虑 dp[i+1][j-1]？当i+1到 j-1的长度小于2时，不需要考虑（因为此时i+1~j-1一定是回文子串/或不存在）。即 j-1-(i+1)+1<2 --> j - i < 3
3、什么时候最长子串改变：每当找到新的回文子串时，将新的回文串长度与之前的max_length作比较。
以下附两种不同递推顺序的代码：
class Solution {
public String longestPalindrome1(String s) {
char[] str=s.toCharArray();
int len=s.length();
if(len < 2){
return s;
}
int maxlen=1,begin=0;
boolean[][] dp = new boolean[len][len];
for(int j=1;j maxlen){ //判断新找到的回文子串是否是最长的
maxlen = j-i+1;
begin = i;
}
}
}
}
return s.substring(begin, begin + maxlen);
}
public String longestPalindrome2(String s) {
char[] str=s.toCharArray();
int len=s.length();
if(len < 2){
return s;
}
int maxlen=1,begin=0;
boolean[][] dp = new boolean[len][len];
for(int l=2;l<=len;l++){ // 按照子串的长度来进行递推
for(int i=0;i= len){break;} // j的长度有可能超出数组长度
if(str[j] != str[i]){
dp[i][j]=false;
}
else{
if(j-i < 3) { dp[i][j]=true; }
else{
dp[i][j] = dp[i+1][j-1];
}
if(dp[i][j] && j-i+1 > maxlen){
maxlen = j-i+1;
begin = i;
}
}
}
}
return s.substring(begin, begin + maxlen);
}
}
这里补一个我当时思考了很久的问题，为什么按子串长度递推的时候，明明是左边界开始，但是每次碰到dp[i+1][j-1]都存在呢？这个需要画图理解。因为是按照子串长度来递推的，dp数组的值就是从主对角线开始斜着一行一行确定的。而 dp[i+1][j-1] 的位置是在 dp[i][j] 的左下角，所以每次dp[i+1][j-1]永远比 dp[i][j] 早一趟确定。（有空补图）
四、Manacher方法：
我们定义一个新概念臂长，表示中心扩展算法向外扩展的长度。如果一个位置的最大回文字符串长度为 2 * length + 1 ，其臂长为 length。
在中心扩展算法中，我们可以得出每个位置的臂长，而这个方法，就是让我们在计算一个新位置的臂长时，利用之前已经计算过的结果减少步骤。（有空再补）
