Longest Palindromic Substring

5. 最长回文子串

分析

中心扩展思想：
- 回文的中心可以是一个字符（如 aba 的中心是 b），也可以是两个字符之间（如 abba 的中心是 bb）
- 遍历字符串的每一个字符（和每一个字符间隙）作为中心，向两侧扩展判断是否为回文子串
具体步骤：
- 枚举每一个可能的中心：
- 单字符中心：如字符 a
- 双字符中心：如字符对 aa
- 每次以当前中心向两侧扩展，直到遇到不相等的字符或边界
- 记录当前最长的回文子串，并与之前记录的结果进行比较，更新最长子串

时间复杂度

遍历字符串每个字符 O(n)，每次从中心向外扩展最多 O(n)，总体时间复杂度为 O(n^2)

空间复杂度

空间复杂度为 O(1)

C++代码

 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


class Solution
{
public:
    string longestPalindrome(string s)
    {
        // 初始化结果变量
        std::string res;

        // 遍历字符串的每一个字符，尝试以其为中心扩展
        for (int i = 0; i < s.size(); ++i)
        {
            // 第一种情况：中心是单个字符
            int l = i - 1, r = i + 1;
            while (l >= 0 && r < s.size() && s[l] == s[r])
                --l, ++r;
            // 更新最长回文子串
            if (res.size() < r - l - 1)
                res = s.substr(l + 1, r - l - 1);

            // 第二种情况：中心是两个字符之间
            l = i, r = i + 1;
            while (l >= 0 && r < s.size() && s[l] == s[r])
                --l, ++r;
            // 更新最长回文子串
            if (res.size() < r - l - 1)
                res = s.substr(l + 1, r - l - 1);
        }

        // 返回最长回文子串
        return res;
    }
};