Python最长回文子串问题

目录

Python最长回文子串

1.暴力解法(Brute Method)2.中心扩散法3.动态规划

python练习–最长回文子串

题目描述解题思路代码

Python最长回文子串


1.暴力解法(Brute Method)

暴力求解是最容易想到的，要截取字符串的所有子串，然后再判断这些子串中哪些是回文的，最后返回回文子串中最长的即可。
这里我们可以使用两个变量，一个记录最长回文子串开始的位置，一个记录最长回文子串的长度，最后再截取。

1. class Solution:
2.   def longestPalindrome(self, s):
3.     if (len(s) < 2):
4.       return s
5.     start = 0 #记录最长回文子串开始的位置
6.     maxLen = 0 #记录最长回文子串的长度
7.     for i in range(len(s) - 1):
8.       for j in range(i,len(s)):#j从i开始，不从i+1开始，s=‘ac就能选第一个‘a'
9.         # 法一：截取所有子串，然后在逐个判断是否是回文的
10.         # 法二（优化）：截取所有子串，如果截取的子串小于等于之前遍历过的最大回文串，直接跳过。
11.              # 因为截取的子串即使是回文串也不可能是最大的，所以不需要判断
12.         if (j - i < maxLen):
13.           continue
14.         if self.isPalindrome(s, i, j) and (maxLen < j - i + 1):
15.         # maxLen为最大长度时，后面maxLen<j-i+1 就为False,能保证截取最长回文字符串
16.           start = i
17.           maxLen = j - i + 1
18.     return s[start:start + maxLen]
20.   # 判断是否是回文串
21.   def isPalindrome(self,s,start,end):
22.     while (start < end) :
23.       if s[start] != s[end]:
24.         return False
25.       start += 1
26.       end -= 1
27.     return True
29. s =  "ac"
30. S = Solution()
31. result = S.longestPalindrome(s)
32. print(result)

复制代码

2.中心扩散法

从左向右遍历：选择一个中心点向两侧扩展，分别考虑奇数组合偶数组的情况。

1. class Solution:
2.   def longestPalindrome(self, s: str) -> str:
3.     # 判断空字符串的情况
4.     if (s == ""):
5.       return ""
6.     result = ""
7.     sSize = len(s)
8.     # 选择一个中心点，向两侧扩展
9.     for i in range(sSize):
10.       # 奇数组情况
11.       tmpStr = self.expandHelper(s, i, i)
12.       # 偶数组情况
13.       tmpStr2 = self.expandHelper(s, i, i + 1)
14.       if len(tmpStr) > len(result):
15.         result = tmpStr
16.       if len(tmpStr2) > len(result):
17.         result = tmpStr2
18.     return result
20.   def expandHelper(self,s,left,right):
21.     sSize = len(s)
22.     while (left >= 0 and right < sSize and s[left] == s[right]):
23.       left -= 1
24.       right += 1
25.     # 小心s[left] != s[right]
26.     return s[(left + 1) : right]
28. s = "aaaabad"
29. S = Solution()
30. result = S.longestPalindrome(s)
31. print(result)

复制代码

3.动态规划

思路与算法
对于一个子串而言，如果它是回文串，并且长度大于 22，那么将它首尾的两个字母去除之后，它依旧是个回文串。例如对于字符串 "ababa''，如果我们已经知道 “bab” 是回文串，那么 “ababa” 一定是回文串，这是因为它的首尾两个字母都是 “a”。
注意：在状态转移方程中，我们是从长度较短的字符串向长度较长的字符串进行转移的，因此一定要注意动态规划的循环顺序。

1. class Solution:
2.   def longestPalindrome(self, s):
3.     n = len(s)
4.     if n < 2:
5.       return s
7.     max_len = 1
8.     begin = 0
9.     # dp[i][j] 表示 s[i..j] 是否是回文串
10.     dp = [[False] * n for _ in range(n)]
11.     for i in range(n):
12.       dp[i][i] = True
14.     # 递推开始
15.     # 先枚举子串长度
16.     for L in range(2, n + 1):
17.       # 枚举左边界，左边界的上限设置可以宽松一些
18.       for i in range(n):
19.         # 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
20.         j = L + i - 1
21.         # 如果右边界越界，就可以退出当前循环
22.         if j >= n:
23.           break
25.         if s[i] != s[j]:
26.           dp[i][j] = False
27.         else:
28.           if j - i < 3:
29.             dp[i][j] = True
30.           else:
31.             dp[i][j] = dp[i + 1][j - 1]#只有dp[0][4]是True,dp[1][3]还是True……,这才是真正的回文串
32.             # dp[i][j] = True #假如s="abaa",s[0]=s[4], d[0][4]=True,就被认为是回文串，跳入下一个环节
34.         # 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
35.         if dp[i][j] and j - i + 1 > max_len:
36.           max_len = j - i + 1
37.           begin = i
38.     return s[begin:begin + max_len]
40. s = "abaa"
41. S = Solution()
42. result = S.longestPalindrome(s)
43. 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）出发最长回文串为多少。
寻找方法：
首先往左寻找与当期位置相同的字符，直到遇到不相等为止。
然后往右寻找与当期位置相同的字符，直到遇到不相等为止。
最后左右双向扩散，直到左和右不相等。

代码

1. class Solution:
2.   def longestPalindrome(self, s: str) -> str:
3.     if not s :
4.       return ""
5.     res = ""
6.     n = len(s)
7.     dp = [[0] * n for _ in range(n)]
8.     max_len = float("-inf")
9.     for i in range(n):
10.       for j in range(i + 1):
11.         if s[i] == s[j] and (i - j < 2 or dp[j + 1][i - 1]):
12.           dp[j][i] = 1
13.         if dp[j][i] and max_len < i + 1 - j:
14.           res = s[j : i + 1]
15.           max_len = i + 1 - j
16.     return res

复制代码

因为我们最后要返回的是具体子串，而不是长度，因此，还需要记录一下maxLen时的起始位置（maxStart），即此时还要maxStart=len
大佬的代码

1. class Solution:
2.   def longestPalindrome(self, s: str) -> str:
3.     n = len(s)
4.     if n < 2:
5.       return s
6.    #中心扩展法，最直观的方法
7.     def center_spread(L: int, R: int) -> str:
8.       while 0 <= L and R < n and s[L]==s[R]:
9.         L -= 1
10.         R += 1
11.       return s[L+1 : R]
13.     res = s[0]
14.     max_len = 1
16.     for i in range(n):
17.       odd_str = center_spread(i, i)
18.       even_str = center_spread(i, i+1)
20.       if len(odd_str) > len(even_str):  #若长度为奇数的长
21.         if len(odd_str) > max_len:
22.           max_len = len(odd_str)
23.           res = odd_str
24.       else:                #若长度为偶数的长
25.         if len(even_str) > max_len:
26.           max_len = len(even_str)
27.           res = even_str
29.     return res

复制代码

以上为个人经验，希望能给大家一个参考，也希望大家多多支持中国红客联盟。