本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer，已开源在github ，欢迎star！
本题来自LeetCode：5. 最长回文子串[1]
题目描述
给定一个字符串
s，找到
s中最长的回文子串。你可以假设
s的最大长度为
1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
暴力法
题目分析
枚举出所有的子串，判断每个子串是否是回文子串。并找到最长的回文子串。这里做了一点小优化，每从一个新的位置，枚举以该位置为起始点的子串时，起始长度为当前最长的回文子串的长度
maxlength。这样能够保证下一个回文子串的长度一定是大于
maxlength的。
题目解答
class Solution {
public String longestPalindrome(String s) {
if(s == null || s.length() == 0) {
return s;
}
int n = s.length();
// 记录最长回文子串的起始位置
int maxBegin = 0;
// 记录最长回文子串的长度
int maxLength = 1;
for(int i = 0; i n; i ++) {
// 这里注意的是，j和i的起始间隔为maxLength
for(int j = i + maxLength; j n; j ++) {
// 若子串[i...j]为回文，那么长度一定比当前maxLength大
if(isPalindrome(s, i, j)) {
maxBegin = i;
maxLength = j - i + 1;
}
}
}
return s.substring(maxBegin, maxBegin + maxLength);
}
//判断子串是否是回文
public boolean isPalindrome(String s, int left, int right) {
while(left right) {
if(s.charAt(left++) != s.charAt(right--)) {
return false;
}
}
return true;
}
}
复杂度分析：
时间复杂度：
O(n^3)
空间复杂度：
O(1)
公共子串
题目分析
这里采用公共子串的解法来解答，可以查看相关的答案解析最长公共子串[2]，由于时间关系，不再详细解析。
题目解答
class Solution {
public String longestPalindrome(String s) {
if(s == null || s.length() == 0) {
return s;
}
int maxLength = 0;
int maxEnd = 0;
int n = s.length();
// 反转该字符串
String reversed = new StringBuilder(s).reverse().toString();
// n + 1的数组，不需要考虑i=0或者j=0的情况
int[][] length = new int[n + 1][n + 1];
for(int i = 1; i = n; i ++) {
for(int j = 1; j = n; j ++) {
// 公共子串
if(s.charAt(i-1) == reversed.charAt(j-1)) {
length[i][j] = length[i - 1][j - 1] + 1;
}
// 若当前公共子串长度大于最大公共子串，则可能为最长回文子串
if(length[i][j] maxLength) {
// 找到reversed中的公共子串起始位置，对应在s中的位置
int ri = n - j + length[i][j];
// 若相等，则表示这是一个回文子串
if(i == ri) {
// 最长回文子串的长度
maxLength = length[i][j];
// 这里记录最长回文子串的结束位置+1
maxEnd = i;
}
}
}
}
return s.substring(maxEnd - maxLength, maxEnd);
}
}
复杂度分析：
时间复杂度：
O(n^2)
空间复杂度：
O(n^2)
继续优化空间复杂度
class Solution {
public String longestPalindrome(String s) {
if(s == null || s.length() == 0) {
return s;
}
int maxLength = 0;
int maxEnd = 0;
int n = s.length();
String reversed = new StringBuilder(s).reverse().toString();
int[] length = new int[n];
for(int i = 0; i n; i ++) {
int preLength = 0;
for(int j = 0; j n; j ++) {
// 公共子串
int temp = length[j];
if(s.charAt(i) == reversed.charAt(j)) {
length[j] = preLength + 1;
} else {
length[j] = 0;
}
preLength = temp;
// 若当前公共子串长度大于最大公共子串，则可能为最长回文子串
if(length[j] maxLength) {
// 找到reversed中的公共子串起始位置，对应在s中的位置
int ri = n - j + length[j] - 2;
// 若相等，则表示这是一个回文子串
if(i == ri) {
// 最长回文子串的长度
maxLength = length[j];
// 这里记录最长回文子串的结束位置+1
maxEnd = i + 1;
}
}
}
}
return s.substring(maxEnd - maxLength, maxEnd);
}
}
复杂度分析：
时间复杂度：
O(n^2)
空间复杂度：
O(n)
更多解法可以查看英文官网的讨论5. Longest Palindromic Substring[3]
参考资料
- Longest Palindromic Substring: https://leetcode.com/problems/longest-palindromic-substring/discuss/?currentPage=1&orderBy=most_votes&query=
原文始发于微信公众号（xiaogan的技术博客）：
