给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
第一种方法
自己未看答案前的做法，也是最容易想到的一种做法。简单来说：就是列举出所有可能的子串，并判断是否是回文子串。但是没有通过力扣系统的时间要求，代码如下：
def longestPalindrome1(s):
i = 0
j = i + 1
# 用来记录最长的回文子串
palStr = ""
while i < len(s):
while j <= len(s):
# 验证是否是回文子串
if s[i:j] == s[i:j][::-1] and len(palStr) < len(s[i:j]):
palStr = s[i:j]
j += 1
i += 1
j = i + 1
return palStr
第二种方法
自己想的一种方法，经多次完善终于通过了力扣系统。但是时间复杂度还是比较高，只是比第一种方法好一点，也能通过力扣系统的时间要求。
主要思想：一个字符串如果是回文字符串，那么它和它的逆序字符串对应位置的相同角标必然字符相等。但是针对一些比较特别的字符串比如："abcdbbfcba"就会得不到正确答案，这时只有当判断到有一连串相等字符的时候，就判断这串字符是否是回文子串（就主要是这步增加了时间复杂度）。
代码如下，也有详细的注释：
def longestPalindrome2(s):
# 用来记录最长的回文子串
palStr = ""
# 将s逆序的字符串
reversedStr = s[::-1]
# 字符串长度
length = len(s)
def getPalindromeStr(s1, reversedStr1):
# 如果传进来的直接就是一个回文字符串，就直接返回
if s1 == reversedStr1:
palStr = s1
return palStr
else:
# 用来记录最终回文子串的开始角标和结束角标
start, end = 0, 0
# 用来记录每次遍历的时候子串相等的第一个角标和最后一个角标
left, right = 0, 0
# 用来记录上一个字符是否相等，默认为False
preEqual = False
for j in range(length - i):
if s1[j] == reversedStr1[j]:
if preEqual:
# 如果上一个字符相等，并且这个字符也相等，就将子串相等的右角标移到现在这个字符
right = j
# 如果这次相等的子串长度大于原来记录的子串长度，并且子串是回文子串
# 就更新最终回文子串的开始和结束角标
if (right - left) > (end - start) and s1[left:right + 1] == s1[left:right + 1][::-1]:
start = left
end = right
else:
# 如果上一个字符不相等，就将子串相等的左角标移到现在这个位置
# 并且将preEqual设置为True
left = j
preEqual = True
else:
# 如果字符不相等，preEqual就为False
preEqual = False
# 返回最终记录的回文子串
return s1[start:end + 1]
for i in range(length):
"""
第一次遍历: 传 cbbd和dbbc进去，如果是回文子串，直接返回
第二次遍历：传 cbb和bbc bbd和dbb 两组数据进去
第三次遍历：传 cb和bc bd和db 两组数据进去
....
如果是回文子串，传进去的正序子串和逆序子串，对应的角标至少相等。
如果出现连续的角标都相等，那么它可能就是回文子串。
再判断它是否是回文子串。
cbbd | cbb[d] | [c]bbd
dbbc | [d]bbc | dbb[c]
| |
| cb[bd] | [cb]bd
| [db]bc | db[bc]
"""
# 将字符串在逆序字符串上方分别每次向左和向右移动一个字符，
pal1 = getPalindromeStr(s[:length-i], reversedStr[I:])
pal2 = getPalindromeStr(s[i:], reversedStr[:length-i])
p = pal1 if len(pal1) > len(pal2) else pal2
if len(p) > len(palStr):
palStr = p
return palStr
第三种方法
看了力扣官方答案过后的写法，主要是利用动态规划的思想。
主要思想：对于一个子串而言，如果它是回文串，并且长度大于 2，那么将它首尾的两个字母去除之后，它仍然是个回文串。具有转态转移的性质，每一步计算都尽量用到了以前的计算结果，这也是典型的空间换时间的算法思想。
就可以得到以下结论：
- 状态：
dp[i][j]表示子串s[i..j]是否为回文子串； - 得到状态转移方程：
dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]；
即是说一个字符串如果是回文，那么它首尾的字符一定相等，并且去掉首尾的子串也是一个回文。 - 边界条件：
(j - 1) - (i + 1) + 1 < 2, 整理得：j - i < 3 <==> j - i + 1 < 4；
边界就是i+1和j-1不能构成区间，也就是长度严格小于2的情况下，dp[i + 1][j - 1]没有意义。j - i + 1 < 4的语义就是当s[i..j]的长度为2或者3的时候，就不用检查子串是否是回文，这时不需要状态转移。 - 初始化：
dp[i][i] = true
dp[i][i]表示对角线上的子串，其实也就是每个单个字符，它一定是回文。其实对角线上的值是不会被其他的状态值所参考。 - 输出：在得到一个状态的值为true的时候，记录起始位置和长度，填表完成以后再截取
状态规划表.png
注意：需要先升序填列保证左下方的值先被算出来，再升序填行，这样就可以参考左下方的值了。
具体代码如下，附有详细注释：
def longestPalindrome3(s):
# 记录字符串长度
length = len(s)
# 如果字符串长度为1，那它本身就是回文
if length < 1:
return s
# 用来记录最大回文子串长度，默认为1
maxlength = 1
# 用来记录最大回文子串的开始位置，默认为0
begin = 0
# dp[i][j]表示子串s[i..j]是否为回文字符串
# 初始化二维表格
dp = [[False] * length for _ in range(length)]
for i in range(length):
# 对角线值初始化为true
dp[i][i] = True
# 因为要先填左下角，也就是先升序填列
# 所以先从j = 1，开始填
j = 1
while j < length:
# 因为对角线已经赋值了，只需要填对角线上方的值即可
# 所以i从0到j-1就好了
i = 0
while i < j:
# 一般将容易的条件写在前面
# 当字符串首尾不相等时，那么它就不是回文
if s[i] != s[j]:
dp[i][j] = False
else:
# 当首尾字符相等的时候，如果去掉首尾后，没有字符了，或者只剩下一个字符，
# 也就是此时整个字符串长度为2或者3时，那它一定是回文
if j - i < 3:
dp[i][j] = True
else:
# 如果整个字符串长度大于3时，就需要参考中间的子串是否是回文
# 也就是填表时需要参考左下角的值，这也就是一个状态转移的过程
dp[i][j] = dp[i + 1][j - 1]
# 只要dp[i][j] == true成立，表示子串s[i..j]是为回文字符串
# 如果子串s[i..j]长度大于记录的最长的回文子串长度，就重新记录回文的起始位置和长度
if dp[i][j] and j - i + 1 > maxlength:
maxlength = j - i + 1
begin = i
i += 1
j += 1
# 最后返回最长的回文子串
return s[begin:begin+maxlength]
复杂度分析
- 时间复杂度：O(n^2)，其中 n 是字符串的长度。动态规划的状态总数为 O(n^2)，对于每个状态，我们需要转移的时间为 O(1)。
- 空间复杂度：O(n^2)，即存储动态规划状态需要的空间。
第四种方法
看了力扣官方答案过后的写法，采用了中心扩展算法。
此方法的本质是：我们枚举所有的「回文中心」并尝试「扩展」，直到无法扩展为止，此时的回文串长度即为此「回文中心」下的最长回文串长度。我们对所有的长度求出最大值，即可得到最终的答案。
中心扩散法
代码如下：
def expandAroundCenter(s, left, right):
"""
根据传进来的挨着的两个角标为中心，在字符串s中尽可能向左右扩展回文子串
"""
# 边界为：left和right不能越界
# 扩展条件为：s[left] == s[right] cbbd
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
# 因为当退出循环的时候，s[left] != s[right]
# 也就是说此时除去首尾字符，中间的子串才是回文字符串，所以返回（left + 1, right - 1）
return left + 1, right - 1
def longestPalindrome4(s):
# 记录字符串长度
length = len(s)
# 用来记录最长回文子串的开始和结束位置
start, end = 0, 0
# 枚举回文中心的位置，最后一个位置没有必要枚举了，因为它不可能再向右扩展了
for i in range(length-1):
# 以i为中心的，最长奇数回文子串的开始和结束位置
# 在expandAroundCenter函数中left和right位置都传i，表示以i为中心
odd_start, odd_end = expandAroundCenter(s, i, i)
# 以i和i+1为中心的，最长偶数回文子串的开始和结束位置
even_start, even_end = expandAroundCenter(s, i, i+1)
# 记录最长的回文子串的开始和结束位置
if odd_end - odd_start > end - start:
start, end = odd_start, odd_end
if even_end - even_start > end - start:
start, end = even_start, even_end
# 返回最长的回文子串
return s[start: end + 1]
复杂度分析
- 时间复杂度：O(n^2)，枚举回文中心位置的个数是2(n-1)，奇数和偶数回文子串情况分别是n-1个，每个回文中心最多会向外扩展O(n)次 。
- 空间复杂度：O(1)，只用到常数个临时变量。
网友评论