5. 最长回文子串
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。
示例 2：
输入: “cbbd”
输出: “bb”
代码
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
44
|
public String longestPalindrome(String s) {
int center = 0;
int rightSide = 0;
int index = 0;
int radius = 0;
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("@");
for (int i = 0; i < s.length(); i++) {
stringBuilder.append(s.charAt(i));
stringBuilder.append("@");
}
String newString = stringBuilder.toString();
int[] ints = new int[newString.length()];
for (int i = 0; i < ints.length; i++) {
if (rightSide > i) {
int left = 2 * center - i;
ints[i] = ints[left];
if (ints[left] + i < rightSide) {
ints[i] = ints[left];
continue;
} else {
ints[i] = rightSide - i;
}
}
while (i - ints[i] - 1 >= 0 && i + ints[i] + 1 < ints.length) {
if (newString.charAt(i - ints[i] - 1) == newString.charAt(i + ints[i] + 1)) {
ints[i]++;
} else {
break;
}
}
rightSide = i + ints[i];
center = i;
if (radius < ints[i]) {
radius = ints[i];
index = i;
}
}
StringBuffer sb = new StringBuffer();
for (int i = index - radius + 1; i <= index + radius; i += 2) {
sb.append(newString.charAt(i));
}
return sb.toString();
}
|
问题： CCC 是cc
近期评论