题目描述

题目链接

给你一个字符串 s，找到 s 中最长的回文子串。

1
2
3
4
5
示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
1
2
3
4
示例 2：

输入：s = "cbbd"
输出："bb"

算法1

(暴力枚举) O(n2)O(n^2)

对于整个字符串，可以有 n 个起点， 每个起点又有 n 个终点，所以枚举所有的情况并找到长度最长的回文子串，复杂度为 O(n2)O(n^2)

(枚举中心点 + 双指针)

可以考虑这么思考： 我们每次枚举的不是子串的起点，而是子串的中心点，那么我们只需要分为如下两种情况

  • 子串的长度为奇数：那么我们枚举的就是中心点，在整个回文子串中，中心点的字符是不需要满足回文条件的，所以只需要向两边扩展，每次比较边界处的两个字符是否相同，若相同那么回文子串可以继续增长；
  • 子串的长度为偶数：那么需要将中心点纳入回文的条件中对比，每次向边界扩展

最终，我们取两种情况中的最长者，即可得到最长的回文子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    string longestPalindrome(string s) {
        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);
        }

        for(int i = 0; i < s.size(); i ++)
        {
            int 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;
    }
};