Leetcode 5 Longest Palindromic Substring DP

Given a string s, return the longest palindromic substring in s.

Solution

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

\[dp[i+1][j-1]\ \&\&\ s[i]=s[j] \]

此时 \(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);     } };