寻找最长的回文子字符串

问题

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

1
2
3
4
5
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example:

1
2
3
Input: "cbbd"
Output: "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
45
46
47
48
public class Solution {
public String longestPalindrome(String s) {
char[] chs = null;
int max = 0;
int len = s.length();
char[] ss = s.toCharArray();
char[] tchs;
int tmax;
for (int index = 0; index < len; index++) {
tchs = new char[len];
tmax = 1;
tchs[index] = ss[index];
for (int i = 1; i <= index && i + index < len; i++) {
if (ss[index - i] != ss[index + i]) {
break;
}
tmax += 2;
tchs[index+i] = ss[index+i];
tchs[index-i] = ss[index-i];
}
if (max < tmax) {
chs = tchs;
max = tmax;
}
tchs = new char[len];
tmax = 0;
for (int i = 0; i <= index && i + index + 1 < len; i++) {
if (ss[index - i] != ss[index + i + 1]) {
break;
}
tmax += 2;
tchs[index-i] = ss[index-i];
tchs[index+i+1] = ss[index+i+1];
}
if (max < tmax) {
chs = tchs;
max = tmax;
}
}
return new String(chs).trim();
}
}