LeetCode hot100-93

https://leetcode.cn/problems/longest-palindromic-substring/description/?envType=study-plan-v2&envId=top-100-liked

5. 最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。

1. 状态定义
   我们用一个二维数组 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);

    }
}