给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。
示例 2：
输入: “cbbd”
输出: “bb”
方法一:暴力匹配(Brute Force)
●根据回文子串的定义，枚举所有长度大于等于2的子串，依次判断它们是否是文;
●在具体实现时，可以只针对大于“当前得到的最长回文子串长度"的子串进行"回文验证”;
●在记录最长回文子串的时候，可以只记录“当前子串的起始位置”和“子串长度”，不必做截取。这一步我们放在后面的方法中实现。
说明:力解法时间复杂度高，但是思路清晰、编写简单。由于编写正确性的可能性很大，可以使用暴力匹配算法检验我们编写的其它算法是否正确。
java
public static String longestPalindrome(String s) {
int len = s.length();
if (len < 2) {
return s;
}
int maxLen = 1;
int begin = 0;
// 每次都会检查下标是否越界，因此先转化成 字符数组
char[] charArray = s.toCharArray();
// 枚举所有长度大于一的子串
for (int i = 0; i < len - 1; i++) {
for (int j = i + 1; j < len; j++) {
if (j - i + 1 > maxLen && validPalindromic(charArray, i, j)) {
maxLen = j - i + 1;
begin = i;
}
}
}
return s.substring(begin, begin + maxLen);
}
/**
* 验证子串是否是回文子串
*
* @param charArray
* @param left
* @param right
* @return
*/
private static boolean validPalindromic(char[] charArray, int left, int right) {
while (left < right) {
if (charArray[left] != charArray[right]) {
return false;
}
left++;
right--;
}
return true;
}
python
class Solution:
# 暴力匹配（超时）
def longestPalindrome(self, s: str) -> str:
# 特判
size = len(s)
if size < 2:
return s
max_len = 1
res = s[0]
# 枚举所有长度大于等于 2 的子串
for i in range(size - 1):
for j in range(i + 1, size):
if j - i + 1 > max_len and self.__valid(s, i, j):
max_len = j - i + 1
res = s[i:j + 1]
return res
def __valid(self, s, left, right):
# 验证子串 s[left, right] 是否为回文串
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
方法二：动态规划
下面是「动态规划』问题的思考路径，供大家参考。
这道题比较烦人的是判断回文子串。因此需要一种能够快速判断原字符串的所有子串是否 是回文子串的方法,于是想到了[动态规划」。
「动态规划」的一个关键的步骤是想清楚「状态如何转移」。实际上回文天然具有「状态转移」性质。
●一个文去掉两头以后，剩下的部分依然是回文(这里暂不讨论边界情况) ; 依然从回文串的定义展开讨论:
●如果一个字符串的头尾两个字符都不相等,那么这个字符串一定不是回文串;
●如果一个字符串的头尾两个字符相等, 有必要继续判断下去。
。如果里面的子串是回文，整体就是回文串;
。如果里面的子串不是回文串,整体就不是文串。
即:在头尾字符相等的情况下，里面子串的回文性质据定了整个子串的回文性质，这就是状态转移。因此可以把「状态」定义为原字符串的一一个子串是否为回文子串。
第1步:定义状态
dp[i][j]|示子串s[i…j] 否为文子串,这里子串s[i… j]义为闭右闭区间，可以取到s[i] 和s[j]。
第2步:思考状态转移方程
在这一粉类讨论(根据头尾字符是否相等)， 根据上面的分析得到:
dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]
说明: .
「动态规划」实上是在填一张二维表格,构成子串，因此i和j的关系是i <= j，因此,只需要填这张
表格对角线以上的部分。
看到dp[i + 1][j-1]就得考虑边界情况。
边界条件是:表达式[i + 1, j- 1]不构成区间,即长度严格小于2，即j-1-(i+1)+1<2，整理得j-i <3。
这个结论很显然: j 一i < 3等价于j一i + 1< 4,即当子串s[i…j]的长等于2或者等于3的时候，实
只需要判断一下头尾两个字符是否相等就可以直接 下结论了。
●如果子串s[i + 1…j- 1]只有1个字符,即去掉两头，剩下中间部分只有1个字符,显然是文;
●如果子串s[i + 1…j-1]为空串，那么子串s[i, j]| -定是回文子串。
因此，在[s[i] == s[j]| 成立和j一i < 3的前提下，直接可以下结论，dp[i][j] = true，否则才执行状态转移。
第3步:考虑初始化
初始化的时候，单个字符一定回文串,因此把对角线先初始化为true, 即dp[i][i] = true。
事实上，初始化的部分都可以省去。因为只有一个字符的时候一定文，dp[i][i] 根本不会被其它状态值所参考。
第4步:考虑输出
只要一得到dp[i][j] = true ，就记录子串的长度和起始位置，没有必要截取,这是因为截取字符串也要消耗性能，记录此时的回文子串的「起始位置」和回文长度」即可。
第5步:考虑优化空间
因为在填表的过程中，只参考了左下方的数值。实上可以优化,但是增加了代码编写和理解的难度
注意事项:总是先得到小子串的回文判定，然后大子串才能参考小子串的判断结果，即填表顺序很重要。
大家能够可以自己动手，画一下表格,相信会对「动态规划」作为一种[表格法」有一个更好的理解。
java
public static String longestPalindrome2(String s) {
int len = s.length();
if (len < 2) {
return s;
}
int maxLen = 1;
int begin = 0;
boolean dp[][] = new boolean[len][len]; // 定义状态：i-j 的子串是否是回文子串
// 每次都会检查下标是否越界，因此先转化成 字符数组
char[] charArray = s.toCharArray();
// 枚举所有长度大于一的子串
for (int i = 0; i < len; i++) {
dp[i][i] = true; // 使对角线为true，因为单个字符一定为回文字符串
}
for (int j = 1; j < len; j++) {
for (int i = 0; i < j; i++) {
if (charArray[i] != charArray[j]) {
dp[i][j] = false;
} else {
if (j - i < 3) {
dp[i][j] = true;// 长度为2的子串回文
} else {
dp[i][j] = dp[i + 1][j - 1];
}
}
// 只要dp[i][j]==true,便记录此刻的最大深度与起始地址
if (dp[i][j] && j - i + 1 > maxLen) {
maxLen = j - i + 1;
begin = i;
}
}
}
return s.substring(begin, begin + maxLen);
}
python
class Solution1:
def longestPalindrome(self, s: str) -> str:
size = len(s)
if size < 2:
return s
dp = [[False for _ in range(size)] for _ in range(size)]
max_len = 1
start = 0
for i in range(size):
dp[i][i] = True
for j in range(1, size):
for i in range(0, j):
if s[i] == s[j]:
if j - i < 3:
dp[i][j] = True
else:
dp[i][j] = dp[i + 1][j - 1]
else:
dp[i][j] = False
if dp[i][j]:
cur_len = j - i + 1
if cur_len > max_len:
max_len = cur_len
start = i
return s[start:start + max_len]
方法三:中心扩散法
采用双指针两边夹，验证是否是回文子串。
除了枚举字符串的左右边界以外，比较容易想到的是枚举可能出现的回文子串的“中心位置”,从“中心位置”尝试尽可能扩散出去，得到一个回文串。
因此中心扩散法的思路是:遍历每一个索引，以这个索引为中心,利用“回文串”中心对称的特点,往两边扩散,看最多能扩散多远。枚举“中心位置”时间复杂度为O(N),从“中心位置扩散得到“回文子串的时间复杂度为O(N),因此时间复杂度可以降到0(N2)。.
在这里要注意一个细节: 回文串在长度为奇数和偶数的时候，“回文中心"的形式是不一样的。
●奇数回文串的"中心"是一 个具体的字符,例如:文串”aba” 的中心是字符"b”;
●偶数回文串的中心是位于中间的两个字符的"空隙”，例如:文串” abba"的中心是两个”b”中间的那个空隙”。
我们可以设计一个方法，兼容以上两种情况:
1、如果传入重合的索引编码,进行中心扩散,此时得到的回文子串的长度是奇数;
2、如果传入相邻的索引编码，进行中心扩散,此时得到的回文子串的长度是偶数。
具体编码细节在以下的代码的注释中体现。
java
public static String longestPalindrome3(String s) {
int len = s.length();
if (len < 2) {
return s;
}
int maxLen = 1;
String res = s.substring(0, 1);
// 中心位置枚举到len-2即可
for (int i = 0; i < len - 1; i++) {
String oddStr = centerSpread(s, i, i);
String evenStr = centerSpread(s, i, i + 1);
String maxLenStr = oddStr.length() > evenStr.length() ? oddStr : evenStr;
if (maxLenStr.length() > maxLen) {
maxLen = maxLenStr.length();
res = maxLenStr;
}
}
return res;
}
private static String centerSpread(String s, int left, int right) {
// TODO Auto-generated method stub
//left==right的是时候，此时回文中心是一个字符。回文串的长度是奇数
//right=left+1 的时候，此时回文中心是一个空隙，回文串的长度是偶数
int len = s.length();
int i = left;
int j = right;
while(i>=0&&j<len) {
if(s.charAt(i)==s.charAt(j)){
i--;
j++;
}else {
break;
}
}
//这里要小心，跳出while循环时，恰好满足s.charAt(i)!=s.charAt(j),因此不能取i,也不能取j
return s.substring(i+1,j);
}
python
class Solution2:
def longestPalindrome(self, s: str) -> str:
size = len(s)
if size < 2:
return s
# 至少是 1
max_len = 1
res = s[0]
for i in range(size):
palindrome_odd, odd_len = self.__center_spread(s, size, i, i)
palindrome_even, even_len = self.__center_spread(s, size, i, i + 1)
# 当前找到的最长回文子串
cur_max_sub = palindrome_odd if odd_len >= even_len else palindrome_even
if len(cur_max_sub) > max_len:
max_len = len(cur_max_sub)
res = cur_max_sub
return res
def __center_spread(self, s, size, left, right):
"""
left = right 的时候，此时回文中心是一个字符，回文串的长度是奇数
right = left + 1 的时候，此时回文中心是一个空隙，回文串的长度是偶数
"""
i = left
j = right
while i >= 0 and j < size and s[i] == s[j]:
i -= 1
j += 1
return s[i + 1:j], j - i - 1
以上便是回文数的全部解法。下面是一种拓展方法，只需要了解思路就行了
方法四: Manacher 算法
Manacher算法是基于“中心扩散法"，采用和kmp算法类似的思想,依然是"以空间换时间"。
Manacher算法,被中国程序员戏称为“马拉车算法。它转用于解决“最长文子串”问题，时间复杂度为O(N)。
维基百科中对于Manacher算法是这样描述的:
[Manacher(1975)]发现了一种线性时间算法，可以在列出给定字符串中从字符串头部开始的所有回文组。Apostolico, Breslauer & Galil (1995)发现，同样的算法也可以在任意位置查找全部最大回文子串，并且时间复杂度是线性的。因此,他们提供了-种时间复杂度为线性的最长回文子串解法。替代性的线性时间解决Jeuring (1994),Gusfield (1997)提供的,基于后缀树(suffix trees)。也存在已知的高效并行算法。
第1步:对原始字符串进行预处理(添加分隔符)
首先在字符串的首尾、相邻的字符中插入分隔符,例如"babad” 添加分隔符”#” 以后得到’ “#b#a#b#a#d#”。
对这-点有如下说明:
第1步:对原始字符串进行预处理(添加分隔符)
首先在字符串的首尾、相邻的字符中插入分隔符,例如"babad” 枷吩隔符”#” 以后得到” #b#a#b#a#d#”。
对这-点有如下说明:
1、分隔符是-一个字符，种类也只有一 个,并且这个字符一定不能是原始字符串中出现过的字符;
2、加入了分隔符以后,使得”间隙”有了具体的位置,方便后续的讨论,新字符串中的任意一个回文子串在原始字符串中
的- -定能找到唯-的一个回文子串与之对应，因此对新字符串的回文子串的研究就能得到原始字符串的回文子串;
3、新字符串的回文子串的长度一定是奇数;
4、新字符串的回文子串一定以分隔符作为两边的边界,因此分隔符起到哨兵”的作用。
第2步:计算辅助数组p
辅助数组p记绿了新字符串中以每个字符为中心的回子串的信息。
手动的计算方法仍然是“中心扩散法”，此时记录以当前字符为中心，向左右两边同时扩散,记绿能够扩散的最大步数。
下面是辅助数组| p的结论:辅助数组p的最大值是5,对应了原字符串” abbabb”的“最长回文子串”:。 这
个结论具有一般性,即:辅助数组 p的最大值就是“最长回文子串”的长度。
因此,我们可以在计算辅助数组p的过程中记录这个最大值,且记录最长回文子串。
最后，不经历风雨,怎能在计算机的大山之顶看见彩虹呢！ 无论怎样，相信明天一定会更好！！！！！
