LEETCODE ALGORITHM:5.Longest Palindromic Substring

发表于 更新于 分类于 Waline： 阅读次数：

题目

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

    Example 1:

    1
    2
    3
    Input: s = "babad"
    Output: "bab"
    Explanation: "aba" is also a valid answer.

    Example 2:

    1
    2
    Input: s = "cbbd"
    Output: "bb"

    Constraints:

    • 1 <= s.length <= 1000
    • s consist of only digits and English letters.

题解

Dp转移方程

\(P(i,j)=P(i+1,j-1)\wedge(S_i==S_j)\)

边界条件

\(P(i,i)=true\)

\(P(i,i+1)=(S_i==S_{i+1})\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    string longestPalindrome(string s) {
        int n=s.size();
        if(n<2) return s;
        int maxl=1;
        int begin=0;
        vector<vector<int>> dp(n,vector<int>(n));
        for(int i=0;i<n;i++) dp[i][i]=1;
        for(int lens=2;lens<=n;lens++){
            for(int i=0;i<n;i++){
                int j=i+lens-1;
                if(j>=n) break;
                if(s[i]!=s[j]){
                    dp[i][j]=0;
                }else{
                    if(j-i<2){
                        dp[i][j]=1;
                    }else{
                        dp[i][j]=dp[i+1][j-1];
                    }
                }
                if(dp[i][j] && j-i+1>maxl){
                    begin=i;
                    maxl=j-i+1;
                }
            }
        }
        return s.substr(begin,maxl);
    }
};