5.最长回文串
题目描述
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = “babad”
输出：”bab”
解释：”aba” 同样是符合题意的答案。
思路
1.暴力解法
2.动态规划
3.中心扩展算法
4.Manacher 算法
注：算法详情请参考leetcode题解
代码
class Solution:
def longestPalindrome(self, s: str) -> str:
"""暴力解法（超出时间限制）"""
# max_len = 0
# longest_palindrome = ""
# for i in range(0, len(s)):
# for j in range(i+1, len(s)+1):
# string = s[i:j]
# # print(string)
# if self.isPalindrome(string):
# if len(string) > max_len:
# max_len = len(string)
# longest_palindrome = string
#
# return longest_palindrome
len_s = len(s)
if len_s < 2:
return s
max_len = 1
begin = 0
# 枚举所有长度严格大于1的字串
for i in range(0, len_s-1):
for j in range(i + 1, len_s):
if j - i + 1 > max_len and self.isPalindrome(s[i: j+1]):
max_len = j - i + 1
begin = i
return s[begin:begin + max_len]
def isPalindrome(self, s: str) -> bool:
"""
筛选+判断（判断反转字符串是否与原字符串相同）
"""
new_s = "".join(ch.lower() for ch in s if ch.isalnum())
return new_s == new_s[::-1]
def longestPalindrome1(self, s: str) -> str:
"""
动态规划算法
一个回文串去掉两头以后，剩下的部分依然是回文
-状态：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
(s[i][j]长度为2或者3时，不用检查字串是否回文)
-初始化：dp[i][i] = true
-输出：在得到一个状态的值为true的时候，记录起始位置和长度，填表完成以后再截取
状态转移方程：dp[i][j] = (s[i] == s[j]) and (j - i < 3 or dp[i + 1][j - 1]
"""
n = len(s)
if n < 2:
return s
max_len = 1
begin = 0
# dp[i][j]表示s[i..j]是否是回文串
dp = [[False] * n for _ in range(n)]
for i in range(n):
dp[i][i] = True
# 注意：先填左下角
for j in range(1, n):
for i in range(0, j):
if s[i] != s[j]:
dp[i][j] = False
else:
if j - i < 3:
dp[i][j] = True
else:
dp[i][j] = dp[i + 1][j-1]
# 只要 dp[i][j] == true 成立，就表示子串 s[i..j] 是回文，此时记录回文长度和起始位置
if dp[i][j] and j - i + 1 > max_len:
max_len = j - i + 1
begin = i
return s[begin:begin + max_len]
def longestPalindrome2(self, s: str) -> str:
"""中心扩展算法"""
start = 0 # 最长回文串的起始位置
end = 0 # 最长回文串的结束位置
for i in range(len(s)):
left1, right1 = self.expandAroundCenter(s, i, i) # 边界情况1：子串长度为1的情况
left2, right2 = self.expandAroundCenter(s, i, i + 1) # # 边界情况2：子串长度为2的情况
if right1 - left1 > end - start: # 扩展的新回文串长度大于当前最长回文串
start, end = left1, right1
if right2 - left2 > end - start:
start, end = left2, right2
return s[start:end + 1]
def expandAroundCenter(self, s, left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return left + 1, right - 1
def expand(self, s, left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return (right - left - 2) // 2
def longestPalindrome3(self, s: str) -> str:
"""Manacher 算法"""
end = -1
start = 0
s = '#' + '#'.join(list(s)) + '#'
arm_len = []
right = -1
j = -1
for i in range(len(s)):
if right >= i:
i_sym = 2 * j - i
min_arm_len = min(arm_len[i_sym], right - i)
cur_arm_len = self.expand(s, i - min_arm_len, i + min_arm_len)
else:
cur_arm_len = self.expand(s, i, i)
arm_len.append(cur_arm_len)
if i + cur_arm_len > right:
j = i
right = i + cur_arm_len
if 2 * cur_arm_len + 1 > end - start:
start = i - cur_arm_len
end = i + cur_arm_len
return s[start + 1:end + 1:2]
if __name__ == '__main__':
slt = Solution()
s = "abad"
res = slt.longestPalindrome(s)
print("最长的回文串为：", res)