5. 最长回文子串

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

示例 1：

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

示例 2：

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

提示：

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母组成

思路：

中心扩散法

以某个或某两个元素为中心，判断当前是否为回文串，然后向左右两侧进行扩充，最终分别计算出偶数长度的回文最大长度和奇数长度的回文最大长度的子串，进行子串截取并返回。

代码：

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
//结果最长回文子串
String res = "";

public String longestPalindrome(String s) {

    //中心扩散法
    int length = s.length();

    //字符串长度小于2，直接返回
    if (length < 2) {
        return s;
    }

    for (int i = 0; i < length - 1; i++) {
        //针对于aba这种形式的回文串，以一个元素为中心
        expandAroundCenter(s, i, i);
        //针对aabb这种形式的回文串，以两个元素为中心
        expandAroundCenter(s, i, i + 1);

    }

    return res;

}

public void expandAroundCenter(String s, int left, int right) {
    //如果当前两端点满足回文串的条件，就向两端进行扩散
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
    }

    //最终最长回文子串的长度
    int len = right - left - 1;

    //更新最终扩展的最长的回文串
    if (len > res.length()) {
        //这里的substring是左闭右开，此时的left和right指向的是最长子串的左一个位置和右一个位置
        res = s.substring(left + 1, right);
    }
    
}