实践出真知
实践出真知

Leetcode 5: 最长回文子串

Timothy Wu 收录于 Leetcode刷题记录
 约 2200 字 预计阅读 5 分钟  - 次阅读  

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

动态规划做法

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

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

按照这个思路：

  • 确定dp数组：dp[i,j]表示字符串[i,j]是否为回文子字符串，其内容为true/false

  • 递推公式（默认i≤j)

    • i==j时，dp[i,j]=true
    • s[i]≠s[j]时，false
    • s[i]=s[j]时，如果其子区间[i+1,j-1]同样回文，则可以递推，反之则不行。也即当dp[i+1,j-1]为true时可以递推

  • 初始值为false，全部为匹配

  • 确定执行顺序（注意边界）：第一个维度需要依赖其后的信息，第二个维度需要依赖前一个的信息。如果横轴为第一个维度，纵轴为第二个维度。

    • 当前为九宫格的中心，则计算出当前结果需要从右下角算出。即遍历顺序为从最右下角向上计算。从下到上，从右到左。因此第一个维度。
    • 执行范围为九宫格的左上三角形。这里可以设置，所有不在当前dp维度内的均为true

  • 尝试一下手填abb

    • 正确
    #include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    string longestPalindrome(string s) {
        vector<vector<bool>> dp(s.length(),vector<bool>(s.length(),false));
        int longest_pos = 0;
        int longest_length = 1;
        for(int j=0;j<s.length();j++){
            for(int i=j;i>=0;i--){
                if(i==j){
                    dp[i][j]=true;
                }
                else if((s[i]==s[j] && dp[i+1][j-1]) || (s[i]==s[j] && i+1 > j-1 )){
                    dp[i][j]=true;
                }
//                if(dp[i][j]){
//                    cout<<i<<" "<<j<<" "<<s.substr(i,j-i+1)<<endl;
//                }
                if(dp[i][j] && j-i+1>longest_length){
                    longest_length = j-i+1;
                    longest_pos = i;
                }
            }
        }
        return s.substr(longest_pos,longest_length);
    }
};

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

    执行用时：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++;
        }
    }
};

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

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

    通过测试用例：180 / 180

    一下子快了很多

马拉车算法

另外有一个专门的算法****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 
CC BY-NC-SA 4.0
计算机/算法/算法题解计算机/算法/字符串计算机/算法/动态规划
返回 | 主页
0%