题目链接：Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

这道题的要求是在字符串中找出最长回文子串。假设字符串长度小于等于1000，而且最长回文子串唯一。

  1. 暴力查找

对每个子串判断是否是回文，遍历每个子串需要两层循环，时间复杂度O(n2)，判断回文时间复杂度是O(n)。这里就不上代码了。。。

时间复杂度：O(n3)

空间复杂度：O(1)

  1. 遍历中心点

由于回文是左右对称的，因此可以遍历字符串选定中心点，然后向两边扫描直到不是回文为止。总共有2n-1个（n个中心点是字符，n-1个中心点是2个相邻字符间隙）中心点，对于每个中心点向两边扫描时时间复杂度O(n)。

时间复杂度：O(n2)

空间复杂度：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

class Solution
{
private:
    int palindrome(string s, int b, int e)
    {
        while(b >= 0 && e < s.size() && s[b] == s[e])
            --b, ++e;
        return e - b - 1;
    }

public:
    string longestPalindrome(string s)
    {
        int b, l = 0;
        for(int i = 0; i < s.size(); ++i)
        {
            int len = max(palindrome(s, i, i), palindrome(s, i, i + 1));
            if(len > l)
            {
                b = i - (len - 1) / 2;
                l = len;
            }
        }
        
        return s.substr(b, l);
    }
};

  1. Manacher算法

Manacher算法是针对寻找最长回文子串的线性算法。

这里不详细介绍了，想要了解的看这里

时间复杂度：O(n)

空间复杂度：O(1)