最长回文子串

Trace

最长回文子串

传送门：https://leetcode-cn.com/problems/longest-palindromic-substring/

Problem

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

示例 1：

1
2
3

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

1 2	输入：s = "cbbd" 输出："bb"

示例 3：

1 2	输入：s = "a" 输出："a"

示例 4：

1 2	输入：s = "ac" 输出："a"

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母（大写和/或小写）组成

方法一：中心扩展

从左往右对每一个元素进行中心扩展，求出以每一位为中心的最长回文子串。

中心扩展顺序：先向左扩展，直到$s[left]!=s[i]$；再向右扩展，直到$s[right]!=s[i]$；最后左右同时扩展，直到$s[left]!=s[right]$；

程序

class Solution {
public:
    // 中心扩展法，n^2
    string longestPalindrome(string s) {
        int maxLen=1;
        int maxStart=0; // 因为需要求出最长回文子串而不仅仅是长度，所以存结果的下标
        int n=s.size();
        int mid=n/2;
        int l=mid,r=mid+1;
        // 从左往右的顺序中心扩展就好，不需要从中间开始
        // 中心拓展顺序：向左拓展，直到不等于s[i];向右拓展，直到不等于s[i];左右同时拓展，直到s[l]!=s[r]
        int left,right;
        int len=1;
        for(int i=0;i<n;i++){
            len=1;
            left=i-1;
            right=i+1;
            while(left>=0&&s[left]==s[i]){
                left--;
                len++;
            }
            while(right<n&&s[right]==s[i]){
                right++;
                len++;
            }
            while(left>=0&&right<n&&s[right]==s[left]){
                right++;
                left--;
                len+=2;
            }
            if(len>maxLen){
                maxLen=len;
                maxStart=left+1;
            }
        }
        return s.substr(maxStart,maxLen);
    }
};C

时间复杂度$O(n^2)$，空间复杂度$O(1)$。

方法二：dp

$dp[i][j]$：字符串$s$的第$i$到第$j$个字符组成的子串是否为回文子串；

对长度大于2的子串，$dp[i][j]=dp[i+1][j-1]\cap s[i]==s[j]$；

若子串的长度为1或2，$dp[i][j]=(s[i]==s[j])$；

由于$dp[i][j]$由$dp[i+1][j-1]$递推而来，即由左下方元素求得，且$i<=j$，所以只有二维矩阵的右上部分有意义，在枚举时注意$i$,$j$顺序。

程序

class Solution {
public:
    // dp[i][j]:s中从i到j这一段字符串是否为回文子串
    // 状态转移: dp[i][j]=dp[i+1][j-1]&&s[i]==s[j]  (i<=j)
    bool dp[1010][1010];
    string longestPalindrome(string s) {
        int maxLen=1;
        int maxStart=0;
        for(int i=0;i<s.size();i++){
            dp[i][i]=true;
        }
        int left,right;
        for(int r=1;r<s.size();r++){
            for(int l=0;l<r;l++){
                if(s[l]==s[r]){
                    // 长度为一或二时
                    if(r-l<=2){
                        dp[l][r]=true;
                    }
                    if(dp[l+1][r-1]){
                        dp[l][r]=true;
                    }
                }
                if(dp[l][r]&&r-l+1>maxLen){
                    maxLen=r-l+1;
                    maxStart=l;
                }
            }
        }
        return s.substr(maxStart,maxLen);
    }
};

时间复杂度：$O(n^2)$，空间复杂度$O(n^2)$

方法三：Manacher 算法

勉强搞懂了原理然而没有板子完全默不出来，放弃了。