最长回文子串(Python)
给一个字符串 s,找到 s 中最长的回文子串。示例 1:输入:s = “babad”输出:“bab”解释:“aba” 同样是符合题意的答案。示例 2:输入:s = “cbbd”输出:“bb”示例 3:输入:s = “a”输出:“a”示例 4:输入:s = “ac”输出:“a”思路一:中心扩散,如果两边的字母相同,就可以继续扩展;如果两边的字母不同,就停止扩展。class Solution:def
给一个字符串 s,找到 s 中最长的回文子串。
示例 1:
输入:s = “babad”
输出:“bab”
解释:“aba” 同样是符合题意的答案。
示例 2:
输入:s = “cbbd”
输出:“bb”
示例 3:
输入:s = “a”
输出:“a”
示例 4:
输入:s = “ac”
输出:“a”
思路一:中心扩散,如果两边的字母相同,就可以继续扩展;如果两边的字母不同,就停止扩展。
class Solution:
def longestPalindrome(self,s):
start, end = 0, 0
for i in range(len(s)):
l1, r1 = self.expandAroundCenter(s, i, i) # 中心为奇数 b a b
l2, r2 = self.expandAroundCenter(s, i, i + 1) # 中心为偶数 b aa b
if r1 - l1 > end - start:
start, end = l1, r1
if r2 - l2 > end - start:
start, end = l2, r2
return s[start:end + 1]
def expandAroundCenter(self,s, l, r):
while l >= 0 and r < len(s) and s[l] == s[r]: # 字母相同,继续扩展
l -= 1
r += 1
return l + 1, r - 1 # 返回下标
if __name__ == '__main__':
s = "babad"
sl = Solution()
print(s.longestPalindrome(s))
思路二:动态规划
1、dp[i][j]数组:表示区间范围[i,j] (左闭右闭)的子串是否是回文子串,如果是dp[i][j]为true,否则为false。
2、递推:dp[i][j] 是回文,那么只有当s[i] == s[j] 时,dp[i+1][j-1] = true(是回文串)。当对于长度为 1 的子串,显然是个回文串;对于长度为 2 的子串,只要两个字母相同,就是一个回文串。
if s[i] == s[j]:
if j - i <= 1: # 子串长度为1或2
dp[i][j] = True
elif dp[i+1][j-1]:
dp[i][j] = True
if dp[i][j] and j - i > r - l: # dp[i][j] 是回文,记录边界
l, r = i, j
3、dp数组初始化:全为False
4、遍历顺序:
a、以矩阵来看,如果是从上到下,从左到右遍历(顺序遍历),那么会用到没有计算过dp[i + 1][j - 1],也就是根据不确定是不是回文的区间[i+1,j-1],来判断[i,j]是不是回文,那结果一定是不对的。所以一定要从下到上,从左到右遍历,这样保证dp[i + 1][j - 1]都是经过计算的。
b、以动态子串:动态规划的边界条件就是子串长度为1或2,从长度较短的字符串向长度较长的字符串进行转移的,dp[i + 1][j - 1]为较短的子串,可以使用,枚举子串长度即可。
"""a、矩阵"""
def dp(s):
lenth = len(s)
l, r= 0, 0
dp = [[False] * lenth for i in range(lenth)]
for i in range(lenth - 1, -1,-1):
for j in range(i,lenth):
if s[i] == s[j]:
if j - i <= 1:
dp[i][j] = True
elif dp[i+1][j-1]:
dp[i][j] = True
if dp[i][j] and j - i > r - l:
l, r = i, j
return s[l:r+1]
"""b、子串长度"""
def dp(s: str) -> str:
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 L in range(2, n + 1):
# 枚举左边界,左边界的上限设置可以宽松一些
for i in range(n):
# 由 L 和 i 可以确定右边界,即 j - i + 1 = L 得
j = L + i - 1
# 如果右边界越界,就可以退出当前循环
if j >= n:
break
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][L] 是回文,记录回文长度和起始位置
if dp[i][j] and j - i + 1 > max_len:
max_len = j - i + 1
begin = i
return s[begin:begin + max_len]
更多推荐
所有评论(0)