Leetcode 5 Longest Palindromic Substring DP(Leetcode 5 Longest Palindromic Substring DP)

Given a string , return the longest palindromic substring in .

s
s

Solution

设 \(dp[i][j]\) 表示字串 \(s[i,…,j]\) 是否为回文串。初始化时,每个单独的字符本身就是回文串;长度为2的串只要首尾相同,也是回文串;长度 \(\geq 3\) 时,只有满足:

此时 \(dp[i][j]\) 也就是回文串。因此循环内侧的 \(i\) 时,应倒序遍历

class Solution {
private:
    bool dp[1003][1003];
    int MAX = -1;
    int ansl, ansr;
    
public:
    string longestPalindrome(string s) {
        int n = s.length();
        for(int i=0;i<n;i++){
            dp[i][i] = true;
            MAX = 1; ansl = i;
        }
        for(int j=1;j<n;j++){
            for(int i=j-1;i>=0;i--){
                if(i+1==j){
                    if(s[i]==s[j])dp[i][j] = true;
                    else dp[i][j] = false;
                }
                else{
                    if(s[i]==s[j] && dp[i+1][j-1])dp[i][j] = true;
                    else dp[i][j] = false;
                }
                if(dp[i][j]){
                    if(MAX<j-i+1)MAX = j-i+1, ansl = i, ansr = j;
                }
            }
        }
        return s.substr(ansl, MAX);
    }
};
————————

Given a string , return the longest palindromic substring in .

s
s

Solution

Set \ (DP [i] [J] \) to indicate whether the string \ (s [I,…, J] \) is a palindrome string. During initialization, each individual character itself is a palindrome string; A string with a length of 2 is also a palindrome string as long as the beginning and end are the same; When the length is \ (\ GEQ 3 \), only:

At this time \ (dp[i][j]\) is the palindrome string. Therefore, when \ (I \) inside the loop, it should be traversed in reverse order

class Solution {
private:
    bool dp[1003][1003];
    int MAX = -1;
    int ansl, ansr;
    
public:
    string longestPalindrome(string s) {
        int n = s.length();
        for(int i=0;i<n;i++){
            dp[i][i] = true;
            MAX = 1; ansl = i;
        }
        for(int j=1;j<n;j++){
            for(int i=j-1;i>=0;i--){
                if(i+1==j){
                    if(s[i]==s[j])dp[i][j] = true;
                    else dp[i][j] = false;
                }
                else{
                    if(s[i]==s[j] && dp[i+1][j-1])dp[i][j] = true;
                    else dp[i][j] = false;
                }
                if(dp[i][j]){
                    if(MAX<j-i+1)MAX = j-i+1, ansl = i, ansr = j;
                }
            }
        }
        return s.substr(ansl, MAX);
    }
};