LeetCode 5. 最长回文子串
原题链接
中等
1.枚举中心点+双指针
class Solution {
/**
* 枚举中心点(奇数+偶数)+ 双指针
*/
public String longestPalindrome(String s) {
int n = s.length();
String res = "";
for(int i = 0; i < n; i ++){
//枚举奇数中心点
int l = i - 1, r = i + 1;
while(l >= 0 && r < n && s.charAt(l) == s.charAt(r)){
l --;
r ++;
}
//因为l和r都已经多减一个1或者多加一个1,因此最终的字符串范围是[l+1,r-1]
if(res.length() < r - l - 1) res = s.substring(l + 1, r);
//枚举偶数中心点
l = i;
r = i + 1;
while(l >= 0 && r < n && s.charAt(l) == s.charAt(r)){
l --;
r ++;
}
if(res.length() < r - l - 1) res = s.substring(l + 1, r);
}
return res;
}
}
2.DP
class Solution {
/**
* dp数组定义:dp[i][j]表示子串s[i,j]是否为回文串
* 递推公式:
dp[i][j] = (s[i] == s[j]) && (dp[i + 1][j - 1])
j - 1 - (i + 1) + 1 < 2 => j - i + 1 < 4 => 表示长度为3或者2的子串是回文串(无需判断)(因为去掉两端后,长度为0或者1)
=> dp[i][j] = (s[i] == s[j]) && (j - i + 1 < 4 || dp[i + 1][j - 1]);
* 初始化:dp[i][i] = true;
* 递推顺序:先枚举j再枚举i,因为d[i][j]可能需要用到dp[i + 1][j - 1];(枚举列)
* 打印dp数组
*/
public String longestPalindrome(String s) {
int n = s.length();
if(n < 2) return s;
boolean[][] dp = new boolean[n][n];
for(int i = 0; i < n; i ++) dp[i][i] = true;
int maxLen = 1;
int startIdx = 0;
for(int j = 1; j < n; j ++){
for(int i = 0; i < j; i ++){
if(s.charAt(i) != s.charAt(j)){
dp[i][j] = false;
}else{
dp[i][j] = (j - i + 1 < 4) || dp[i + 1][j - 1];
// 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){
startIdx = i;
maxLen = j - i + 1;
}
}
}
return s.substring(startIdx, startIdx + maxLen);
}
}