LeetCode 05 最长回文子串

Posted on Edited on In

LeetCode 05 最长回文子串

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

示例 1：

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

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

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母组成
通过次数1,194,472提交次数3,217,315

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：
首先理解回文字符串，根据长度可分为两种：
长度为偶数的回文串，例：abba
长度为奇数的回文串，例：aba
那么我们可以这样理解，
如果是奇数回文串，可从中间位置依次往两边扫描，每次扫描左右位置字符相等
如果是偶数回文串，从中间两个位置依次两边扫描，每次扫描左右位置字符相等
每次扫描到最长位置后记录长度，取最大长度的回文串返回即可

图解：
过程如下图示: (橙色代表遍历奇数回文串位置，橙色和青色一起代表遍历偶数回文串位置)
aeceece
⬆ 
最长为 "a"
aeceece
⬆ 
最长为 "e"
aeceece
⬆ 
最长为 "ece"
aeceece
⬆ 
最长为 "e"
aeceece
⬆ ⬆ 
最长为 "eceece"
aeceece
⬆ 
最长为 "e"
aeceece
⬆ 
最长为 "ece"
aeceece
⬆ 
最长为 "e"


因此返回最长回文串为 "eceece"

代码：
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
public String longestPalindrome(String s) {
    if (s.length() == 0 || s.length() == 1) return s;
    char[] chars = s.toCharArray();
    String maxString = String.valueOf(chars[0]);
    for (int i = 0; i < chars.length; i++) {
        int n = 0;
        int len = 1;
        while (i - n - 1 >= 0 && i + n + 1 < chars.length && chars[i - n - 1] == chars[i + n + 1]) {
            n++;
            len += 2;
        }
        if (len > maxString.length()) {
            maxString = s.substring(i - n, i + n + 1);
        }
        if (i + 1 < chars.length && chars[i] == chars[i + 1]) {
            n = 0;
            len = 2;
            while (i - n - 1 >= 0 && i + 1 + n + 1 < chars.length && chars[i - n - 1] == chars[i + 1 + n + 1]) {
                n++;
                len += 2;
            }
            if (len > maxString.length()) {
                maxString = s.substring(i - n, i + 1 + n + 1);
            }
        }
    }
    return maxString;
}