LeetCode 5 最长回文子串

发表于 更新于 分类于
本文字数： 2k 阅读时长 ≈ 2 分钟 
1
2
3
4
5
6
7
8
9
10
11
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

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

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

第一种普通的算法，O(n^2)

第二种manacher算法，O(n)

第一种

从中间位置向两边扩展，对于一个中间位置的扩展操作为O(n)

遍历中间位置，中间位置可能是某个字符，也可能在某两个字符之间，遍历操作复杂度O(2n)
总的时间复杂度O(n^2), 空间复杂度O(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
27
28
29
30
31
32
33
34
class Solution {
public:
    string longestPalindrome(string s) {
        if(s.size()<1)
            return "";
        int start, end, len;
        start = end = len = 0;
        for(int i=1;i<2*s.size();++i)
        {
            int l,r;
            if(i&1)
                l = r = i>>1;
            else
            {
                l = (i-1)>>1;
                r = (i+1)>>1;
            }
            while(s[l]==s[r]&&l>=0&&r<s.size())
            {
                --l;
                ++r;
            }
            --r;
            ++l;
            if(r-l+1>len)
            {
                len = r-l+1;
                start = l;
                end = r;
            }
        }
        return s.substr(start, len);
    }
};

manacher算法

解析

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
char str[3000];
int len[3000];
char res[3000];
int min(int x, int y){ return x<y?x:y;}
char* longestPalindrome(char* s) {
    int id,mx,max_len;
    id = mx = max_len = 0;
    str[0] = '$';
    int k=1;
    for(int i=0;s[i]!='\0';++i)
    {
        str[k++] = '#';
        str[k++] = s[i];
    }
    str[k++] = '#';
    str[k] = '\0';
    int start,end;
    for(int i=1;i<k;++i)
    {
        if(i<mx)
            len[i] = min(len[2*id-i], mx-i);
        else
            len[i] = 1;
        while(str[i+len[i]]==str[i-len[i]])
            ++len[i];
        if(len[i]+i>mx)
        {
            mx = len[i]+i;
            id = i;
        }
        if(len[i]-1>max_len)
        {
            max_len = len[i]-1;
            start = i-max_len;
            end = i+max_len;
        }
    }
    k = 0;
    for(int i=start;i<=end;++i)
        if(i%2==0)
            res[k++] = str[i];
    res[k] = '\0';
    return res;
}