LeetCode5 最长回文字串

发表于 | 分类于 |
字数统计: 460 | 阅读时长 ≈ 2

链接： https://leetcode-cn.com/problems/implement-strstr/

题面

给定字符串str，找出其最长回文子串

解法

动态规划 区间dp 时间复杂度O(n^2)

Manacher算法 比较复杂 时间复杂度O(n)

代码

dp

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
class Solution {
public:
    string longestPalindrome(string s) {
        int len = s.size(), maxlen = 1, begin = 0;
        if (len < 2) return s;
        vector<vector<int>> dp(len, vector<int>(len));
        for (int i = 0; i < len; i++) {
            dp[i][i] = 1;
        }

        for (int L = 2; L <= len; L++) {
            for (int i = 0; i < len; i++) {
                int j = L + i - 1;
                if (j >= len) break;
                if (s[i] == s[j]) {
                    if (j - i < 3) dp[i][j] = 1; // 偶数长度回文
                    else dp[i][j] = dp[i + 1][j - 1];
                }

                if (dp[i][j] && j - i + 1 > maxlen) {
                    maxlen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substr(begin, maxlen);
    }
};

Manacher’s Algorithm

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
class Solution {
public:
    int explore(string& s, int i) { // 由中心向外探索回文串
        int len = 1, siz = s.size();
        while(i - len >= 0 && i + len < siz && s[i - len] == s[i + len]) {
            len++;
        }
        return len * 2 - 1;
    }
    string longestPalindrome(string s) {
        int len = s.size(), maxlen = 0;
        string str = "$";
        for (int i = 0; i < len; i++) { // 将所有的偶数长度子串补全为奇数长度
            str += s[i];
            str += "$";
        }
        len = len * 2 + 1;
        vector<int> cen(len);
        for (int i = 0; i < len;) {
            int l = explore(str, i);
            maxlen = max(maxlen, l);
            if (l <= 3) {
                cen[i++] = l;
            }
            else {
                int loc = i;
                cen[i] = l;
                for (int j = 1; j <= l / 2; j++) {
                    int temp = loc - j - cen[loc - j] / 2;
                    i = loc + j;
                    if (temp > loc - l / 2) {
                        cen[loc + j] = cen[loc - j];
                    }
                    else if (temp < loc - l / 2) {
                        cen[loc + j] = cen[loc - j] - (loc - l / 2 - temp) * 2;
                    }
                    else {
                        cen[loc + j] = cen[loc - j];
                        break;
                    }
                }
            }
            if (i + l / 2 == len - 1) break;
        }
        string ret = "";
        for (int i = 0; i < len; i++) {
            if (cen[i] == maxlen) {
                for (int j = i - maxlen / 2; j <= i + maxlen / 2; j++) {
                    if (str[j] != '$') ret += str[j];
                }
                break;
            }
        }
        return ret;
    }
};