算法题：找出最长回文子串

发表于 分类于 阅读次数： 阅读次数：

今天刷到一道很经典的算法题：找出字符串的最长回文子串，常见的思路是中心扩散，算法是dp，但是题解中有两个十分优秀的算法，特作记录

算法一：暴力(O(n^2))(TLE)

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
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    string longestPalindrome(string s) {
        string ans = "";
        int n_max = 0;
        for(int i = 0; i < s.size(); ++i){
            int n = 1;
            string res(1, s[i]);
            for(int j = 1; ; ++j){
                if(i - j < 0 || i + j >= s.size() || s[i - j] != s[i + j]){
                    break;
                }
                else{
                    n += 2;
                    res = s[i - j] + res + s[i + j];
                    // cout << i << ' ' << res << endl;
                }
            }
            if(n > n_max){
                n_max = n;
                ans = res;
            }
        }
        for(int i = 0; i < s.size(); ++i){
            int n = 1;
            string res = "";
            for(int j = 0; ; j ++){
                if(i - j < 0 || i + j + 1 >= s.size() || s[i - j] != s[i + j + 1]){
                    break;
                }
                else{
                    n += 2;
                    res = s[i - j] + res + s[i + 1 + j];
                }
            }
            if(n > n_max){
                n_max = n;
                ans = res;
            }
        }
        return ans;
    }
};

算法二：DP(O(n^2))

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if (n < 2) {
            return s;
        }

        int maxLen = 1;
        int begin = 0;
        // dp[i][j] 表示 s[i..j] 是否是回文串
        vector<vector<int>> dp(n, vector<int>(n));
        // 初始化：所有长度为 1 的子串都是回文串
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
        // 递推开始
        // 先枚举子串长度
        for (int L = 2; L <= n; L++) {
            // 枚举左边界，左边界的上限设置可以宽松一些
            for (int i = 0; i < n; i++) {
                // 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                int j = L + i - 1;
                // 如果右边界越界，就可以退出当前循环
                if (j >= n) {
                    break;
                }

                if (s[i] != s[j]) {
                    dp[i][j] = false;
                } else {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }

                // 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substr(begin, maxLen);
    }
};

// 真-中心扩散
class Solution {
public:
    pair <int, int> f(const string& s, int l, int r){
        while(l >= 0 && r < s.size() && s[l] == s[r]){
            l --;
            r ++;
        }
        return {l + 1, r - 1};
    }
    string longestPalindrome(string s) {
        int n = s.size();
        if(n < 1){
            return "";
        }
        int st = 0, ed = 0;
        for(int i = 0; i < n; ++i){
            const auto &[l1, r1] = f(s, i, i);
            const auto &[l2, r2] = f(s, i, i + 1);
            cout << i << ' ' << l1 << ' ' << r1 << ' ' << l2 << ' ' << r2 << endl;
            // auto [l1, r1] = f(s, i, i);
            // auto [l2, r2] = f(s, i, i + 1);
            if((r1 - l1 + 1) > (ed - st + 1)){
                st = l1;
                ed = r1;
            }
            if(r2 - l2 + 1 > ed - st + 1){
                st = l2;
                ed = r2;
            }
        }
        return s.substr(st, ed - st + 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
class Solution {
    public String longestPalindrome(String s) {

        int length = s.length();
        String maxStr="";
        String reverse=new StringBuffer(s).reverse().toString();

        int x=0;
        int y=1;
        while (x<length&&y<=length){
            String substring = s.substring(x, y);
            if (reverse.contains(substring)){
                if(substring.equals(new StringBuffer(substring).reverse().toString()))
                if (substring.length()>maxStr.length()){
                    maxStr=substring;
                }
                y++;
            }else {
                x++;
                y=x+1;
            }
        }

        return maxStr;
    }
}

算法四：Manacher算法(O(n))

详见：https://leetcode.cn/problems/longest-palindromic-substring/solutions/255195/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/