Leetcode 5: 最长回文子串

千灵域

发布于 2022-06-17 12:55:18

1910

发布于 2022-06-17 12:55:18

文章被收录于专栏：challenge filterchallenge filter

5 最长回文子串

找到的题解：

对于给定的字符串，返回其最长的回文子串。难度倒是不高，就是比较麻烦。

朴素暴力写法

最先想到的当然是朴素的暴力写法：从头开始枚举所有的子串，直到找到回文子串

#include <iostream>

using namespace std;

bool judgePalindrome(string s){
    for(int i=0;i<s.length()/2;i++){
        if(s[i]!=s[s.length()-i-1]){
            return false;
        }
    }
    return true;
}

class Solution {
public:
    string longestPalindrome(string s) {
        int longest_length = 0;
        int longest_pos = 0;
        for(int i=0;i<s.length();i++){
            // 重复尝试所有的开头

            // 然后尝试枚举长度，长度最小为当前的最大长度
            for(int j=s.length()-i;j>longest_length;j--){
                //判断是否为回文子串
                bool result = judgePalindrome(s.substr(i,j));
                if(result){
                    longest_pos = i;
                    longest_length = j;
                    break;
                }
            }
        }
        return s.substr(longest_pos,longest_length);
    }
};

int main() {
    Solution s;
    cout<<s.longestPalindrome("abccb")<<endl;
    return 0;
}

复杂度为O(n^3)，n为字符串长度。结果不出意外的超时了。

缓存探索回文点写法

另外的一个想法是，既然要判断最长的回文子串，那首先要回文。要回文，首先要相等。因此先跑一遍，用字典记录下所有字符以及其相等的位置。（已知字符仅包括数字和英文字母）

一个想法是，根据所有的相等情况从大到小枚举可能的回文点范围，并记录下回文点的位置，做一次探测。

考虑到回文子串的嵌套特性同一回文点记录回文中心和回文上界，如果长度为偶数则记录0.5。

这样，构建回文相等map的复杂度为O(n)，探索所有的相等可能性为O(n^2)，叠加上对回文串的检查一样是O(n^3)。只是由于进行了很多记忆，并且只在相等情况下搜索，因此常数项相对来说会小很多。

这个思路的一个基本想法是：对于一个更长的字符串，如果以其中心点的更小长度内曾经探明没有回文子串，那么这个子串一定不回文。

#include <iostream>
#include <map>
#include <vector>
#include <math.h>
using namespace std;

bool judgePalindrome(string s){
    for(int i=0;i<s.length()/2;i++){
        if(s[i]!=s[s.length()-i-1]){
            return false;
        }
    }
    return true;
}

class Solution {
public:
    string longestPalindrome(string s) {
        int longest_length = 0;
        int longest_pos = 0;
        map<char,vector<int>> store;
        map<double,int> record; // record[i]=j表示在回文点i上探索过的最大长度为j
        for(int i=0;i<s.length();i++){
            store[s[i]].push_back(i);
        }
        for ( const auto &myPair : store ) {
            // 遍历所有的key
//            cout<<myPair.first<<endl;
            auto arr = myPair.second;
            if(arr.size()<=1) {
                continue;
            }
//            for(int i=0;i<arr.size();i++){
//                cout<<arr[i]<<" ";
//            }
//            cout<<endl;
            for(int i=0;i<arr.size();i++){
                for(int j=i+1;j<arr.size();j++){
                    int pos1 = arr[i];
                    int pos2 = arr[j];
                    double mid_point = (double)(pos1+pos2)/2;
                    int cur_length = ceil(pos2-mid_point);
                    // 如果在record中有，就不进行记录
                    bool isRecord = false;
                    if(record.find(mid_point)!=record.end()){
                        if(record[mid_point]<=cur_length){
                            isRecord = true;
                        }
                    }
                    if(isRecord) {
                        continue;
                    }
                    else if(pos2-pos1+1<longest_length){
                        continue;
                    }
                    // 无记录，则进行搜索
                    bool result = judgePalindrome(s.substr(pos1,pos2-pos1+1));
                    if(result){
                        longest_length = pos2-pos1+1;
                        longest_pos = pos1;
                    }else{
                        // 如果小的字符串内部没有回文，那么更大的长度也不会有
                        record[mid_point] = cur_length;
                    }
                }
            }
        }
        if(longest_length==0){
            longest_length = 1;
            longest_pos = 0;
        }
        return s.substr(longest_pos,longest_length);
    }
};

结果挺一般的，也就属于做出来的级别

执行用时：708 ms, 在所有 C++ 提交中击败了8.91%的用户

内存消耗：322.3 MB, 在所有 C++ 提交中击败了28.12%的用户

通过测试用例：180 / 180

动态规划做法

此外，由于回文子串的可扩展性，是具备最优子结构的。因此这道题可以考虑用动态规划来做

确定dp数组的大小，以及其内容，代表的含义
写dp的递推公式
dp的初始值是多少
dp应该如何开始遍历，或者采用记忆化搜索的形式？
举个例子推导dp数组

按照这个思路：

执行用时：428 ms, 在所有 C++ 提交中击败了**34.57%**的用户

内存消耗：29.4 MB, 在所有 C++ 提交中击败了**48.89%**的用户

通过测试用例：180 / 180

双指针方法

该方法的想法是尝试扩展。回文字符串一定是从某个中心出发的，这个中心可能是一个字符或者两个字符，因此总共应该有n+n-1个中心。

class Solution {
public:
    int left = 0;
    int right = 0;
    int maxLength = 0;
    string longestPalindrome(string s) {
        int result = 0;
        for (int i = 0; i < s.size(); i++) {
            extend(s, i, i, s.size()); // 以i为中心
            extend(s, i, i + 1, s.size()); // 以i和i+1为中心
        }
        return s.substr(left, maxLength);
    }
    void extend(const string& s, int i, int j, int n) {
        while (i >= 0 && j < n && s[i] == s[j]) {
            if (j - i + 1 > maxLength) {
                left = i;
                right = j;
                maxLength = j - i + 1;
            }
            i--;
            j++;
        }
    }
};

马拉车算法

另外有一个专门的算法****Manacher's Algorithm****

该算法可以解决最长回文子字符串问题，时间复杂度为线性

```cpp
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

string preprocess(string s){
    int n=s.length();
    if(n==0){
        return "^$";
    }
    string ret = "^";
    for(int i=0;i<n;i++){
        ret = ret + "#" + s[i];
    }
    ret += "#$";
    return ret;
}

class Solution {
public:
    string longestPalindrome(string s) {
        string T = preprocess(s);
        int n = T.length();
        vector<int> P(n,0);
        int C=0,R=0;
        for(int i=1;i<n-1;i++){
            int i_mirror=2*C-i;
            if(R>i){
                P[i] = min(R-i,P[i_mirror]);
            }else{
                P[i] = 0;
            }

            while(T[i+1+P[i]] == T[i-1-P[i]]){
                P[i] ++;
            }

            if(i+P[i]>R){
                C=i;
                R=i+P[i];
            }
        }

        int maxLen = 0;
        int centerIndex = 0;
        for(int i=1;i<n-1;i++){
            if(P[i] > maxLen){
                maxLen = P[i];
                centerIndex = i;
            }
        }
        int start = (centerIndex - maxLen) / 2;
        return s.substr(start,maxLen);
    }
};

int main() {
    Solution s;
    cout<<s.longestPalindrome("cbbd")<<endl;
    return 0;
}
```

执行用时：**84 ms**, 在所有 C++ 提交中击败了**62.05%**的用户

内存消耗：**312.5 MB**, 在所有 C++ 提交中击败了**28.35%**的用户

通过测试用例：**180 / 180**

但是这个算法实在是有点复杂

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-04-05，如有侵权请联系 cloudcommunity@tencent.com 删除

c++