LeetCode 5. Longest Palindromic Substring (最长回文子串)

本是古典何须时尚 2022-05-14 09:17 172阅读 0赞

题目描述：

给定一个字符串 **s**，找到 **s** 中最长的回文子串。你可以假设 **s** 的最大长度为1000。

示例1：

输入: "babad"
    输出: "bab"
    注意: "aba"也是一个有效答案。

示例2：

输入: "cbbd"
    输出: "bb"

Accepted C++ Solution:

**1. 改进的中心扩展方法：**

将原字符串扩展成\#a\#b\#c\#的形式可以直接枚举长度,不用考虑回文串长度的奇偶性

class Solution {
    public:
        string longestPalindrome(string s) {
            string str = "", ans = "";
            int len = s.length();
            int maxl = -1, cnt;
            //  将原字符串扩展成#a#b#c#的形式可以直接枚举长度,不用考虑回文串长度的奇偶性
            for (int i = 0; i < len; i++) {
                str += '#';
                str += s[i];
            }
            str += '#';
            
            for (int i = 1; i < 2 * len; i++) {
                cnt = 0;
                while ((i-cnt >= 0) && (i + cnt <= 2 * len) && (str[i-cnt] == str[i+cnt]))    //在中心周围扩展
                    cnt ++;
                cnt --;
                if (cnt > maxl) {
                    maxl = cnt;
                    ans  = s.substr((i-cnt)/2, (i+cnt)/2 - (i-cnt)/2);
                }
            }
            return ans;
        }
    };

2.动态规划

假设dp\[ i \]\[ j \]的值为true，表示字符串s中下标从 i 到 j 的字符组成的子串是回文串。那么可以推出：

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

这是一般的情况，由于需要依靠i+1, j -1，所以有可能 i + 1 = j -1, i +1 = (j - 1) -1，因此需要求出基准情况才能套用以上的公式：

a. i + 1 = j -1，即回文长度为1时，dp\[ i \]\[ i \] = true;

b. i +1 = (j - 1) -1，即回文长度为2时，dp\[ i \]\[ i + 1\] = （s\[ i \] == s\[ i + 1\]）。

有了以上分析就可以写出代码了。需要注意的是动态规划需要额外的O(n2)的空间。

class Solution {
    public:
        string longestPalindrome(string s) {
            if(s.size()==0) return "";
            int i = 0, j = 0;
            int n = s.size();
            
            //initialize P[n][n], we only need half of P, and initialize it like: (e.g. : s="abbc")
            bool P[n][n]={false};
            for(int x = 0;x<n;x++){
                P[x][x]=true;
                if(x==n-1) break;
                P[x][x+1] = (s[x]==s[x+1]);
            }
            //dp 
            for(int i = n-3; i>=0; --i){    //左端
                for(int j = i+2;j<n; ++j){    //右端
                    P[i][j] = (P[i+1][j-1] && s[i]==s[j]);     
                }
            }
            //get maxstr result
            int max = 0;
            string maxstr = "";
            for(int i=0;i<n;i++){
                for(int j=i;j<n;j++){
                    if(P[i][j]==true and j-i+1>max){
                        max = j-i+1;
                        maxstr = s.substr(i,j-i+1);
                    }
                }
            }
            return maxstr;
        }
    };

最优方案：Manacher's Algorithm O(n)

[Manacher][]

（暂时还没懂 - -）

[Manacher]: https://articles.leetcode.com/longest-palindromic-substring-part-ii/