题目描述
给你一个字符串 s，找到 s 中最长的 回文 子串。
示例 1：
输入：s = “babad”
输出：”bab”
解释：”aba” 同样是符合题意的答案。
示例 2：
输入：s = “cbbd”
输出：”bb”
提示：
1 <= s.length <= 1000s 仅由数字和英文字母组成
思路
遍历所有字串
开始的思路是暴力求解，直接遍历字符串，将由每个字符开头的所有长度为 1、2、3… 的所有子串都拿出来，逐一判断，记下最大长度。思路简单，但是效率太低，测试用例的长度超过 100 个字符，直接超时。
双指针
遍历字符串中，使用两个指针，从当前字符开始，然后判断两个指针位置的字符是否相等。如果相等，则两个指针分别向前、向后移动一位，继续比较，直到两个指针处的字符不相等，记录下两个指针间的字符拼接的字符串。如果有向后的指针到达字符串结尾，则结束比较，后面不会再有更长的回文子串了。
后面发现这种方法只能处理长度为奇数的子串，会遗漏比如 “ABBA” 这种长度为偶数的回文子串。
于是在此基础上改进，遍历两遍字符串，分别处理两种情况。
代码实现
Java 代码实现如下：
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
43
| public static String maxLengthOfSubString(String s) {
char[] charArray = s.toCharArray();
String r = "";
for (int i = 0; i < charArray.length; i++) {
int p1 = i;
int p2 = i;
while (p1 >= 0 && p2 < charArray.length && charArray[p1] == charArray[p2]) {
p1--;
p2++;
}
String tmp = new String(charArray, p1 + 1, (p2 - 1) - (p1 + 1) + 1);
if (tmp.length() > r.length()) {
r = tmp;
}
if (p2 == charArray.length - 1) {
break;
}
}
for (int i = 0; i < charArray.length - 1; i++) {
int p1 = i;
int p2 = i + 1;
while (p1 >= 0 && p2 < charArray.length && charArray[p1] == charArray[p2]) {
p1--;
p2++;
}
String tmp = new String(charArray, p1 + 1, (p2 - 1) - (p1 + 1) + 1);
if (tmp.length() > r.length()) {
r = tmp;
}
if (p2 == charArray.length - 1) {
break;
}
}
return r;
}
|
后续 LeetCode 的做题记录只记录一些个人感觉有难度或者是解法比较精妙的题。