原文链接: Longest Palindromic Substring
找到最长回文字符串是一个经典的编码面试问题，本文总结了针对这个问题的3中不同的解决方案。
- 动态程序
让s成为输入字符串，i和j是字符串的两个索引。定义一个二维数组“table”，让table[i][j]表示从i到j的子字符串是否为回文。
更改条件:
table[i+1][j-1] == 1 && s.charAt(i) == s.charAt(j)
=>
table[i][j] == 1
时间 O(n^2) 空间 O(n^2)
public String longestPalindrome(String s) {
if(s==null || s.length()<=1)
return s;
int len = s.length();
int maxLen = 1;
boolean [][] dp = new boolean[len][len];
String longest = null;
for(int l=0; l<s.length(); l++){
for(int i=0; i<len-l; i++){
int j = i+l;
if(s.charAt(i)==s.charAt(j) && (j-i<=2||dp[i+1][j-1])){
dp[i][j]=true;
if(j-i+1>maxLen){
maxLen = j-i+1;
longest = s.substring(i, j+1);
}
}
}
}
return longest;
}
例如, 如果输入字符串是"dabcba", 最终的矩阵如下:
1 0 0 0 0 0
0 1 0 0 0 1
0 0 1 0 1 0
0 0 0 1 0 0
0 0 0 0 1 0
0 0 0 0 0 1
从表中,我们可以清楚地看到,最长的字符串是table[1][5]。
- 简单的算法
时间 O(n^2), 空间 O(1)
public String longestPalindrome(String s) {
if (s.isEmpty()) {
return null;
}
if (s.length() == 1) {
return s;
}
String longest = s.substring(0, 1);
for (int i = 0; i < s.length(); i++) {
// get longest palindrome with center of i
String tmp = helper(s, i, i);
if (tmp.length() > longest.length()) {
longest = tmp;
}
// get longest palindrome with center of i, i+1
tmp = helper(s, i, i + 1);
if (tmp.length() > longest.length()) {
longest = tmp;
}
}
return longest;
}
// Given a center, either one letter or two letter,
// Find longest palindrome
public String helper(String s, int begin, int end) {
while (begin >= 0 && end <= s.length() - 1 && s.charAt(begin) == s.charAt(end)) {
begin--;
end++;
}
return s.substring(begin + 1, end);
}
- 曼切尔算法
尽管它将带来O(n)时间复杂度的好处，但曼切尔算法的计算要复杂得多。因为它不是典型的，所以没有必要浪费时间。
