最长回文子串Python
给一个字符串 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]
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhfjagce
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
photoshop蒙版画笔没反应怎么办
PHP中文网 06-24