https://leetcode.cn/problems/longest-palindromic-substring/description/?envType=study-plan-v2&envId=top-100-liked
5. 最长回文子串
给你一个字符串 s,找到 s 中最长的回文子串。
- 状态定义
我们用一个二维数组 dp[i][j] 表示子串 s[i…j] 是否是回文:
dp[i][j] = true 表示子串 s[i…j] 是回文;
dp[i][j] = false 表示子串 s[i…j] 不是回文。
2. 状态转移方程
要判断子串 s[i…j] 是否是回文,需要满足以下两个条件:
两端字符相等:s[i] == s[j]
内部子串 s[i+1…j-1] 也是回文:dp[i+1][j-1] = true
因此状态转移方程为:
dp[i][j]=(s[i]==s[j]) && (j−i<2 ∣∣ dp[i+1][j−1])
如果子串长度为 1(j - i == 0),它本身是回文。
如果子串长度为 2(j - i == 1),只需判断 s[i] == s[j]。
如果子串长度大于 2(j - i > 1),还需要判断 dp[i+1][j-1] 是否为 true。
这题去遍历各种子串的循环有点意思。外层是字符串长度从1到n。内层是子串的起始位置。子串的结束位置j是i和len算出来的。
class Solution {
public String longestPalindrome(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
int maxLen = 1;
int start = 0;
for(int len = 1;len<=n;len++){
for(int i=0;i<=n-len;i++){
int j = i+len-1;
if(s.charAt(i)==s.charAt(j)){
if(len<=2){
dp[i][j]=true;
} else{
dp[i][j]=dp[i+1][j-1];
}
}
if(dp[i][j] && len>maxLen){
maxLen = len;
start = i;
}
}
}
return s.substring(start,start+maxLen);
}
}