Python最長回文子串問題

更新時間：2022年11月03日 08:59:38 作者：AII派森

這篇文章主要介紹了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=‘a(chǎn)c'就能選第一個‘a(chǎn)'
? ? ? ? ? ? ? ? # 法一：截取所有子串，然后在逐個判斷是否是回文的
? ? ? ? ? ? ? ? # 法二（優(yōu)化）：截取所有子串，如果截取的子串小于等于之前遍歷過的最大回文串，直接跳過。
? ? ? ? ? ? ? ? ? ? ? ? ? # 因為截取的子串即使是回文串也不可能是最大的，所以不需要判斷
? ? ? ? ? ? ? ? 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.中心擴散法

從左向右遍歷：選擇一個中心點向兩側(cè)擴展，分別考慮奇數(shù)組合偶數(shù)組的情況。

class Solution:
? ? def longestPalindrome(self, s: str) -> str:
? ? ? ? # ?判斷空字符串的情況
? ? ? ? if (s == ""):
? ? ? ? ? ? return ""
? ? ? ? result = ""
? ? ? ? sSize = len(s)
? ? ? ? # 選擇一個中心點，向兩側(cè)擴展
? ? ? ? for i in range(sSize):
? ? ? ? ? ? # 奇數(shù)組情況
? ? ? ? ? ? tmpStr = self.expandHelper(s, i, i)
? ? ? ? ? ? # 偶數(shù)組情況
? ? ? ? ? ? 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.動態(tài)規(guī)劃

思路與算法

對于一個子串而言，如果它是回文串，并且長度大于 22，那么將它首尾的兩個字母去除之后，它仍然是個回文串。例如對于字符串 "ababa''，如果我們已經(jīng)知道 “bab” 是回文串，那么 “ababa” 一定是回文串，這是因為它的首尾兩個字母都是 “a”。

注意：在狀態(tài)轉(zhuǎn)移方程中，我們是從長度較短的字符串向長度較長的字符串進行轉(zhuǎn)移的，因此一定要注意動態(tài)規(guī)劃的循環(huán)順序。

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):
? ? ? ? ? ? # 枚舉左邊界，左邊界的上限設(shè)置可以寬松一些
? ? ? ? ? ? for i in range(n):
? ? ? ? ? ? ? ? # 由 L 和 i 可以確定右邊界，即 j - i + 1 = L 得
? ? ? ? ? ? ? ? j = L + i - 1
? ? ? ? ? ? ? ? # 如果右邊界越界，就可以退出當前循環(huán)
? ? ? ? ? ? ? ? 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,就被認為是回文串，跳入下一個環(huán)節(jié)
?
? ? ? ? ? ? ? ? # 只要 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 僅由數(shù)字和英文字母（大寫和/或小寫）組成

解題思路

中心擴展法：

把每個字母（或者數(shù)字）當成回文串的中心，這里要考慮兩種情況，回文串的長度為奇數(shù)或者偶數(shù)情況。

從每一個位置出發(fā)，向兩邊擴散即可。傳遞下去的條件是s[L]==s[R]；

遇到不是回文的時候結(jié)束。

eg: str = “acdbbdaa”。需要尋找從第一個b（位置為3）出發(fā)最長回文串為多少。

尋找方法：

首先往左尋找與當期位置相同的字符，直到遇到不相等為止。

然后往右尋找與當期位置相同的字符，直到遇到不相等為止。

最后左右雙向擴散，直到左和右不相等。

代碼

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): ? ?#若長度為奇數(shù)的長
? ? ? ? ? ? ? ? if len(odd_str) > max_len:
? ? ? ? ? ? ? ? ? ? max_len = len(odd_str)
? ? ? ? ? ? ? ? ? ? res = odd_str
? ? ? ? ? ? else: ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? #若長度為偶數(shù)的長
? ? ? ? ? ? ? ? if len(even_str) > max_len:
? ? ? ? ? ? ? ? ? ? max_len = len(even_str)
? ? ? ? ? ? ? ? ? ? res = even_str
? ? ? ??
? ? ? ? return res

以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。

您可能感興趣的文章: