Python最长回文子串问题
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
# 判断是否是回文串
def isPalindrome(self,s,start,end):
while (start < end) :
if s != s:
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 == s):
left -= 1
right += 1
# 小心s != s
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 表示 s 是否是回文串
dp = [ * n for _ in range(n)]
for i in range(n):
dp = 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 != s:
dp = False
else:
if j - i < 3:
dp = True
else:
dp = dp#只有dp是True,dp还是True……,这才是真正的回文串
# dp = True #假如s="abaa",s=s, d=True,就被认为是回文串，跳入下一个环节
# 只要 dp == true 成立，就表示子串 s 是回文，此时记录回文长度和起始位置
if dp and j - i + 1 > max_len:
max_len = j - i + 1
begin = i
return s
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==s；
遇到不是回文的时候结束。
eg: str = “acdbbdaa”。需要寻找从第一个b（位置为3）出发最长回文串为多少。
寻找方法：
首先往左寻找与当期位置相同的字符，直到遇到不相等为止。
然后往右寻找与当期位置相同的字符，直到遇到不相等为止。
最后左右双向扩散，直到左和右不相等。
代码
class Solution:
def longestPalindrome(self, s: str) -> str:
if not s :
return ""
res = ""
n = len(s)
dp = [ * n for _ in range(n)]
max_len = float("-inf")
for i in range(n):
for j in range(i + 1):
if s == s and (i - j < 2 or dp):
dp = 1
if dp and max_len < i + 1 - j:
res = s
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==s:
L -= 1
R += 1
return s
res = s
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://www.jb51.net/article/266577.htm
免责声明：由于采集信息均来自互联网，如果侵犯了您的权益，请联系我们【E-Mail:cb@itdo.tech】 我们会及时删除侵权内容，谢谢合作！
页:
[1]