5.-longest-palindromic-substring-1.md

5. Longest Palindromic Substring

{% tabs %} {% tab title="CPP" %}

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if (n <= 1)  return s;
        vector<vector<bool>> dp(n,vector<bool>(n,false));
        
        for (int i = 0 ; i < n ; ++i){
            dp[i][i] = true;
        }
        int start = 0;
        int cur = 0;
        int max_ = 1;
        for (int i = n - 2; i > -1 ; --i){
            for (int j = i + 1; j < n; ++j) {
                
                if (s[i] == s[j]){
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }else {
                    dp[i][j] = false;
                }
                if (dp[i][j]) {
                    cur = j - i + 1;
                    if (cur > max_) {
                        max_ = cur;
                        start = i;
                    }
                }
            }
// 这才是返回string
        } return s.substr(start, max_);
    }
};

{% endtab %}

{% tab title="Python" %}

class Solution:
    def longestPalindrome(self, s: str) -> str:
        
        if len(s) <= 1:
            return s
        ## dp(i,j) s[i:j+1] = True
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = True
            
        start = 0
        max_ = 1
        ## 主要是要在对角线开始 往上
        for i in range(n - 2, -1,-1):
            for j in range(i + 1, n):
                if s[i]== s[j]:
                    if j - i < 3:
                        dp[i][j] = True
                    else:
                        dp[i][j] = dp[i + 1][j - 1]
                        
                else:
                    dp[i][j] = False
                    
                if dp[i][j]:
                    curr = j - i + 1
                    if curr > max_:
                        max_ = curr
                        start = i
        return s[start:start + max_]
        

{% endtab %} {% endtabs %}