看见题目，觉得哪种解法写起来都挺麻烦，所以先上一个暴力解法吧，判断回文数借助了题目palindrome-number中的思想，不过复杂度已经到 O(n^3)了，算法耗时也已经超过天际了，大概只超过了 3%的人吧。
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
| class Solution {
public String longestPalindrome(String s) {
char[] sc=s.toCharArray();
if(sc.length<=1)
return s;
int longest=0;
int left=0;
int right=0;
for(int i=0;i<sc.length;i++){
for(int j=i+1;j<=sc.length;j++){
boolean needUpdate=true;
for(int m=i,n=j-1;m<=n;m++,n--){
if(sc[m]!=sc[n]){
needUpdate=false;
break;
}
}
if(needUpdate && j-i+1>longest){
longest=j-i+1;
left=i;
right=j;
}
}
}
return s.substring(left,right);
}
}
|
sigh，又拖了一周。
接着，参考网上的动态规划的思路，可以建立一个数组，将以前的结果进行记录。之前判断过的串都可以被利用起来。
参考博客: https://www.cnblogs.com/grandyang/p/4464476.html
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
| class Solution {
public String longestPalindrome(String s) {
char[] sc=s.toCharArray();
if(sc.length<=1)
return s;
boolean[][] dp = new boolean[sc.length][sc.length];
int longest=0;
int left=0;
int right=0;
for(int i=0;i<sc.length;i++){
dp[i][i]=true;
for(int j=0;j<i;j++){
if(sc[i]==sc[j] && (i-j<2 || dp[j+1][i-1])){
dp[j][i]=true;
if(i-j+1>longest){
longest=i-j+1;
left=j;
right=i;
}
}
}
}
return s.substring(left,right+1);
}
}
|
最后，是 Manacher’s Algorithm，也叫马拉车算法。使用这个算法使用空间换取时间，十分巧妙地将算法的时间复杂度降到 O(n)。
主要参考了https://blog.csdn.net/insistgogo/article/details/12287805和http://www.cnblogs.com/grandyang/p/4475985.html这两篇文章。
算法的主要地方在于构建回文串半径数组，只要它被填充完，最大回文串就能找到。而算法中方采取了一个关键方式来构建它：
1
| p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;
|
这个关键算法和最大回文串半径的长度有关。具体可以参考上面的两篇文档，文档搬运到此结束，我就不当稳当搬运工了。
这个方法的确很有意思，值得再去回味。
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
| class Solution {
public String longestPalindrome(String s) {
char[] sc=s.toCharArray();
StringBuilder sb=new StringBuilder("$#");
for(int i=0;i<sc.length;i++){
sb.append(sc[i]);
sb.append('#');
}
char[] nsc=sb.toString().toCharArray();
int[] p=new int[nsc.length];
int id=0;
int mx=0;
int resLen=0;
int resCenter=0;
for(int i=0;i<nsc.length;i++){
p[i] = mx>i ? Math.min(p[2*id-i], mx-i) : 1;
while(i-p[i]>=0 && i+p[i]<nsc.length && nsc[i+p[i]]==nsc[i-p[i]]) p[i]++;
if(mx<i+p[i]){
mx=i+p[i];
id=i;
}
if(resLen<p[i]){
resLen=p[i];
resCenter=i;
}
}
return s.substring((resCenter-resLen)/2,(resCenter-resLen)/2+resLen-1);
}
}
|