Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example:
Input: "cbbd"
Output: "bb"
解题思路：
最长回文子串，一句话总结：暴力 O(n^3)，改进 O(n^2)，Manacher O(n) 【马拉车算法】。
看到过一篇写马拉车算法比较好的文章：马拉车算法
由于马拉车理解起来比较困难，这里提出两种 O(n^2) 的解题思路，在 Leetcode 上可以AC。
思路1： 所有的回文串都是对称的。长度为奇数回文串以最中间字符的位置为对称轴左右对称，而长度为偶数的回文串的对称轴在中间两个字符之间的空隙。我们知道整个字符串中的所有字符，以及字符间的空隙，都可能是某个回文子串的对称轴位置。可以遍历这些位置，在每个位置上同时向左和向右扩展，直到左右两边的字符不同，或者达到边界。对于一个长度为n的字符串，这样的位置一共有n+n-1=2n-1个，在每个位置上平均大约要进行n/4次字符比较，于是此算法的时间复杂度是O(n^2)，空间复杂度 O(1)。
思路2： 动规 dp[i][j]。我们知道，像最长公共子串、最长公共子序列，以及最长回文子串、最长回文子序列等问题都可以采用动态规划的思路解决。在字符串 s 中，dp[i][j] 表示 s[i...j] 子序列的最优解。
设状态 f(i,j) 表示区间 s[i...j] 是否为回文串，则状态转移方程为
| true i=j
f(i,j) = | s[i]=s[j] j=i+1
| s[i]=s[j] and f(i+1,j-1) j>i+1
只需要开辟一个二维 bool 空间，记录子序列最优解即可。时间复杂度 O(n^2)，空间复杂度 O(n^2)。
Python 实现（思路1）：
class Solution:
# AC版本：时间复杂度：O(n^2)， 空间复杂度：O(1)
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
lens = len(s)
if lens <= 0:
return s
substr, maxLen = '', 0
i = 1
while i <= 2 * lens - 1: # 一共有 2*(lens-1) 个判断回文的位置
j = i // 2
k = 1
if i % 2: # 是字符
while j - k >= 0 and j + k < lens:
if s[j-k] == s[j+k]:
k += 1
else:
break
# k 为失配的间距
sublen = (k - 1) * 2 + 1 # 子回文串的长度
if sublen > maxLen:
maxLen = sublen
substr = s[j-k+1:j+k] # 更新最大回文子串
else: # 是间隙
while j - k >= 0 and j + k - 1< lens:
if s[j-k] == s[j+k-1]:
k += 1
else:
break
# k 为失配的间距
sublen = (k - 1) * 2 # 子回文串的长度
if sublen > maxLen:
maxLen = sublen
substr = s[j-k+1:j+k-1] # 更新最大回文子串
i += 1
return substr
a = 'babad'
b = 'abbd'
c = 'eabcbaabcd'
d = 'aba'
e = 'abba'
print(Solution().longestPalindrome(a)) # 'bab'
print(Solution().longestPalindrome(b)) # 'bb'
print(Solution().longestPalindrome(c)) # 'cbaabc'
print(Solution().longestPalindrome(d)) # 'aba'
print(Solution().longestPalindrome(e)) # 'abba'
Java 实现（思路2）：
public Solution {
public static String a(String s) {
int left=0, right=0; // 回文串区间的上、下标
int maxLen=1; // 回文串之间的长度
// 初始化f(i,j)，记录 [i,j] 之间是否为回文串
boolean[][] dp=new boolean[s.length()][s.length()];
for (int k=0; k<s.length(); k++) {
for (int i=0; i+k<s.length(); i++) {
int j=i+k;
// 一个字符肯定为true
if (i==j) dp[i][j]=true;
// 比较当前两个字符（如bb），如果相等，则该区间一定为true
if (j==i+1 && s.charAt(i)==s.charAt(j))
dp[i][j]=true;
// 比较当前两个字符（如b...b），如果相等，则该区间取决于dp[i+1][j-1]是否为true
if (j>i+1 && s.charAt(i)==s.charAt(j))
dp[i][j]=dp[i+1][j-1];
// 更新最大子串的上、下标和长度
if (dp[i][j] && maxLen<j-i+1) {
maxLen=j-i+1;
left=i;
right=j;
}
}
}
// substring返回上、下标之间的字符串（左闭右开，故right+1）
return s.substring(left, right+1);
}
public static void main(String[] args) {
String s=new String("civiathmeaweherehighlyresol");
System.out.println(a(s)); //hereh
}
}
