题解 | #最长回文子串#
最长回文子串
http://www.nowcoder.com/practice/b4525d1d84934cf280439aeecc36f4af
动态规划 区间dp
设f[i][j]为[i,j]能够形成回文串，如果s[i] == s[j] && (i + 1 > j - 1 || f[i + 1][j - 1])，那么即为回文串
i + 1 > j - 1：形如aa这样的形式
f[i + 1][j - 1]：更一般的形式 abba
import java.util.*;
/*
区间dp
*/
public class Solution {
public int getLongestPalindrome(String A, int n) {
boolean f[][] = new boolean[n + 10][n + 10];
for(int i = 0;i < n;i++)f[i][i] = true;
int res = 1;
for(int len = 2;len <= n;len++){
for(int i = 0;i < n;i++){
int j = i + len - 1;
if(j >= n)continue;
if(A.charAt(i) == A.charAt(j)){
if(i + 1 > j - 1 || f[i + 1][j - 1]){
f[i][j] = true;
res = Math.max(res,len);
}
}
}
}
return res;
}
}
O(n^2) O(n^2)
查看20道真题和解析