Leetcode 05
Published:
最长回文子串
最长回文子串 [medium]
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。
Example
1.
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
2.
输入: "cbbd"
输出: "bb"
思路
P(i,j) 表示字符串 s 的第 i 到 j 个字母组成的串是否为回文串
动态规划方程：
P(i,j)=P(i+1,j−1)∧(Si==Sj)
(i,j)取决于(i+1,j−1)，所以是从左下角开始遍历，即一列一列遍历。
当j-i<3时，子串长度为1，2，3。
时间复杂度：O(n^2)
空间复杂度：O(n^2)
Solution
class Solution {
public String longestPalindrome(String s) {
int l = s.length();
if (l<2){
return s;
}
boolean [][]dp = new boolean[l][l];
char[] chs = s.toCharArray();
int maxlen = 1, begin =0;
for (int i=0;i<l;i++){
dp[i][i] = true;
}
// dp[i,j] = dp[i+1,j-1] and chs[i] == chs[j]
for (int j=1; j<l;j++){
for (int i=0;i<j;i++){
if (chs[i] != chs[j]){
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);
}
}