Python最长回文子串问题
作者:AII派森 发布时间:2023-10-02 16:13:21
Python最长回文子串
1.暴力解法(Brute Method)
暴力求解是最容易想到的,要截取字符串的所有子串,然后再判断这些子串中哪些是回文的,最后返回回文子串中最长的即可。
这里我们可以使用两个变量,一个记录最长回文子串开始的位置,一个记录最长回文子串的长度,最后再截取。
class Solution:
def longestPalindrome(self, s):
if (len(s) < 2):
return s
start = 0 #记录最长回文子串开始的位置
maxLen = 0 #记录最长回文子串的长度
for i in range(len(s) - 1):
for j in range(i,len(s)):#j从i开始,不从i+1开始,s=‘ac'就能选第一个‘a'
# 法一:截取所有子串,然后在逐个判断是否是回文的
# 法二(优化):截取所有子串,如果截取的子串小于等于之前遍历过的最大回文串,直接跳过。
# 因为截取的子串即使是回文串也不可能是最大的,所以不需要判断
if (j - i < maxLen):
continue
if self.isPalindrome(s, i, j) and (maxLen < j - i + 1):
# maxLen为最大长度时,后面maxLen<j-i+1 就为False,能保证截取最长回文字符串
start = i
maxLen = j - i + 1
return s[start:start + maxLen]
# 判断是否是回文串
def isPalindrome(self,s,start,end):
while (start < end) :
if s[start] != s[end]:
return False
start += 1
end -= 1
return True
s = "ac"
S = Solution()
result = S.longestPalindrome(s)
print(result)
2.中心扩散法
从左向右遍历:选择一个中心点向两侧扩展,分别考虑奇数组合偶数组的情况。
class Solution:
def longestPalindrome(self, s: str) -> str:
# 判断空字符串的情况
if (s == ""):
return ""
result = ""
sSize = len(s)
# 选择一个中心点,向两侧扩展
for i in range(sSize):
# 奇数组情况
tmpStr = self.expandHelper(s, i, i)
# 偶数组情况
tmpStr2 = self.expandHelper(s, i, i + 1)
if len(tmpStr) > len(result):
result = tmpStr
if len(tmpStr2) > len(result):
result = tmpStr2
return result
def expandHelper(self,s,left,right):
sSize = len(s)
while (left >= 0 and right < sSize and s[left] == s[right]):
left -= 1
right += 1
# 小心s[left] != s[right]
return s[(left + 1) : right]
s = "aaaabad"
S = Solution()
result = S.longestPalindrome(s)
print(result)
3.动态规划
思路与算法
对于一个子串而言,如果它是回文串,并且长度大于 22,那么将它首尾的两个字母去除之后,它仍然是个回文串。例如对于字符串 "ababa'',如果我们已经知道 “bab” 是回文串,那么 “ababa” 一定是回文串,这是因为它的首尾两个字母都是 “a”。
注意:在状态转移方程中,我们是从长度较短的字符串向长度较长的字符串进行转移的,因此一定要注意动态规划的循环顺序。
class Solution:
def longestPalindrome(self, s):
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[0][4]是True,dp[1][3]还是True……,这才是真正的回文串
# dp[i][j] = True #假如s="abaa",s[0]=s[4], d[0][4]=True,就被认为是回文串,跳入下一个环节
# 只要 dp[i][L] == true 成立,就表示子串 s[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]
s = "abaa"
S = Solution()
result = S.longestPalindrome(s)
print(result)
python练习–最长回文子串
题目描述
给你一个字符串 s,找到 s 中最长的回文子串。
示例:
输入:s = “babad”
输出:“bab”
解释:“aba” 同样是符合题意的答案。
输入:s = “cbbd”
输出:“bb”
输入:s = “a”
输出:“a”
输入:s = “ac”
输出:“a”
提示:
1 <= s.length <= 1000
s 仅由数字和英文字母(大写和/或小写)组成
解题思路
中心扩展法:
把每个字母(或者数字)当成回文串的中心,这里要考虑两种情况,回文串的长度为奇数或者偶数情况。
从每一个位置出发,向两边扩散即可。传递下去的条件是s[L]==s[R];
遇到不是回文的时候结束。
eg: str = “acdbbdaa”。需要寻找从第一个b(位置为3)出发最长回文串为多少。
寻找方法:
首先往左寻找与当期位置相同的字符,直到遇到不相等为止。
然后往右寻找与当期位置相同的字符,直到遇到不相等为止。
最后左右双向扩散,直到左和右不相等。
代码
class Solution:
def longestPalindrome(self, s: str) -> str:
if not s :
return ""
res = ""
n = len(s)
dp = [[0] * n for _ in range(n)]
max_len = float("-inf")
for i in range(n):
for j in range(i + 1):
if s[i] == s[j] and (i - j < 2 or dp[j + 1][i - 1]):
dp[j][i] = 1
if dp[j][i] and max_len < i + 1 - j:
res = s[j : i + 1]
max_len = i + 1 - j
return res
因为我们最后要返回的是具体子串,而不是长度,因此,还需要记录一下maxLen时的起始位置(maxStart),即此时还要maxStart=len
大佬的代码
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
if n < 2:
return s
#中心扩展法,最直观的方法
def center_spread(L: int, R: int) -> str:
while 0 <= L and R < n and s[L]==s[R]:
L -= 1
R += 1
return s[L+1 : R]
res = s[0]
max_len = 1
for i in range(n):
odd_str = center_spread(i, i)
even_str = center_spread(i, i+1)
if len(odd_str) > len(even_str): #若长度为奇数的长
if len(odd_str) > max_len:
max_len = len(odd_str)
res = odd_str
else: #若长度为偶数的长
if len(even_str) > max_len:
max_len = len(even_str)
res = even_str
return res
来源:https://blog.csdn.net/weixin_42698464/article/details/121389797
猜你喜欢
- 但是Class这个东西,如果用得比较少,充其量只是一个大模块的包装方式. 只有大规模地用它来开发,才能显出它对项目管理的优越性来. 所谓的意
- 由于XML本身的诸多优点,XML技术已被广泛的使用,目前的好多软件技术同XML紧密相关,比如微软的.net 平台对xml提供了强大的支持,提
- 2022-09-29shell操作:我在使用中是pycharm与数据库建立连接的一个工具。使用的环境:在此处是用在了虚拟环境中。使用场景:一
- Go pongo2 教程展示了如何使用 pongo2 模板引擎在 Golang 中使用模板。模板引擎是一个库,旨在将模板与数据结合起来以生成
- 直角三角形rows = int(input('输入列数:'))for i in range(1, rows):print(&
- 一、先来看看Python星空图代码绘制成品1 两个人的星空星空下,欲执子之手,相倚长青树。看皎洁月色,闻乡间气息,赏佳人芳心。2 明月相伴的
- 之前对mac os系统自带的python进行了升级,结果发现新安装的python的site-packages目录并没有加到python的系统
- *注意:本文的内容涉及到修改NTFS磁盘权限和设置安全策略,请务必在确认您了解操作可能的后果之后再动手进行任何的修改。文中提及的权限都是在原
- 1. 介绍-- PHP5添加了一项新的功能:Reflection。这个功能使得phper可以reverse-engineer class,
- 本文实例主要实现Python中的文件复制操作,有两种方法,具体实现代码如下所示:#coding:utf-8 # 方法1:使用read()和w
- 效果图实例代码如下:<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transit
- 本文实例讲述了Python设计模式之观察者模式。分享给大家供大家参考,具体如下:观察者模式是一个软件设计模式,一个主题对象包涵一系列依赖他的
- Postman生成okhttp代码依赖<dependency>  
- 在开发数据库应用中,经常会遇到处理时间的问题,如查询指定时间的记录等。下面就这些常见的问题,结合自己的一些经验,和大家探讨一下这类问题。首先
- 一、lambda关键字的使用方法func=lambda x:x+1print(func(1))#2print(func(2))#3#以上la
- PHP children() 函数实例查找 note 节点的子节点:<?php $note=<<<XML<no
- 一、给定一个日期值,求出此日期所在星期的星期一和星期天的日期数据 例如给定一个日期 2010-09-01,求出它所在星期的星期一是2010-
- 在编程时你一定碰到过时间触发的事件,在VB中有timer控件,而asp中没有,假如你要不停地查询数据库来等待一个返回结果的话,我想你一定知道
- 前言人脸识别在LWF(Labeled Faces in the Wild)数据集上人脸识别率现在已经99.7%以上,这个识别率确实非常高了,
- 前言图片是Word的一种特殊内容,这篇文章主要介绍了关于Python操作word文档,向里面插入图片和表格的相关内容,下面话不多说了,来一起