5. 最长回文子串

Posted on | In
Words count in article: 249 | Reading time ≈ 1

题目

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例1

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

示例2：

1
2
输入: "cbbd"
输出: "bb"

解法

解法一：

Java

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) {
        const int len = s.size();
        if(len <= 1)return s;
        string str = preProcess(s);
        int n = str.size(), id = 0, mx = 0;
        vector<int>p(n, 0);
        for(int i = 1; i < n-1; i++)
        {
            p[i] = mx > i ? min(p[2*id-i], mx-i) : 1;
            while(str[i+p[i]] == str[i-p[i]])p[i]++;
            if(i + p[i] > mx)
            {
                mx = i + p[i];
                id = i;
            }
        }
         
        int maxLen = 0, index = 0;
        for(int i = 1; i < n-1; i++)
            if(p[i] > maxLen)
            {
                maxLen = p[i];
                index = i;
            }
        return s.substr((index - maxLen)/2, maxLen-1);
    }
    string preProcess(const string &s)
    {
        int n = s.size();
        string res; 
        res.push_back('$');
        res.push_back('#');
        for(int i = 0; i < n; i++)
        {
            res.push_back(s[i]);
            res.push_back('#');
        }
        res.push_back('^');
        return res;
    }
};
0%