坑人，网上搜索出来的很多递归求最大回文子串的代码是错误的，
输入 “TBSABT”
返回 “TBSABT”
不过，下面这个实现也有问题，
输入 “TBSABT” ，应该返回啥？ “T”？返回"B"是不是也是对的？最大回文子串是不是要限制最小长度，为1就不算？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
public String longestPalindrome(String s) {
String result = "";
int length = s.length();
boolean[][] dp = new boolean[length][length];
for(int maybeMaxLength = 0;maybeMaxLength<length;maybeMaxLength++){
for(int beginIndex = 0;beginIndex+maybeMaxLength<length;beginIndex++){
int endIndex = beginIndex+maybeMaxLength;
if(maybeMaxLength == 0){
dp[beginIndex][endIndex] = true;
}else if(maybeMaxLength == 1){
dp[beginIndex][endIndex] = (s.charAt(beginIndex)==s.charAt(endIndex));
}else{
dp[beginIndex][endIndex] = dp[beginIndex+1][endIndex-1]&&(s.charAt(beginIndex)==s.charAt(endIndex));
}
if(dp[beginIndex][endIndex]&& maybeMaxLength+1>result.length()){
result = s.substring(beginIndex,endIndex+1);
}
}
}
return result;
}
|