概念

回文字符串是指一個字符串從左到右與從右到左遍歷得到的序列是相同的。例如“abcba“就是回文字符串，而"abcab"則不是回文字符串。

回文字符串給定一個字符串，求它最長的回文子串長度，例如輸入字符串'35534321'，它的最長回文子串是'3553'，所以返回4。

方法

求回文字符串的方法

目錄

概念

方法

1. 暴力枚舉法

2. 中心搜索法

3. 中心擴展法

github地址

---

分析與解答：

最容易想到的方法為遍歷字符串所有可能的子串（暴力法），判斷其是否為回文字符串看，然后找出最長的回文字串。但是當字符串很長的時候，這種方法的效率是非常低下的，因此這種方法不可取。

給定字符串"",假設p(i, j)=1表示“”是回文字符串；P(i, j)=0表示“”不是回文字符串；

如果:那么P(i, i+1)=1,否則P(i, i+1) =0.

如過:那么P(i+1, j+1)=p(i, j).?
————————————————
版權聲明：本文為CSDN博主「灬蠟筆灬」的原創文章，遵循CC 4.0 BY-SA版權協議，轉載請附上原文出處鏈接及本聲明。
原文鏈接：https://blog.csdn.net/qq_42013574/article/details/88825930

1. 暴力枚舉法

從長到短遍歷，找到所有子串,判斷每一個子串是否是回文.即a==a[::-1]

參考：https://blog.csdn.net/wangweimic/article/details/93977486

# 從長到短，依次遍歷判斷所有的子字符串,st= st[::-1] def get_reverstring(string):substring_length = len(string)while substring_length > 0:for i in range(len(string) - substring_length + 1):# 因為從長到短，需要遍歷[0:17]；[0:16]、[1:17]...，所以需要另一個循環在每次更新要檢測的子字符串長度時，重置上面的range()函數.# i從一開始的0到0，1到0，1，2，是在被減去的數值范圍內循環遍歷# 另一方面，依次遞減需要檢測的子字符串的長度，直到子字符串為空，長度為0，這是一個典型的while循環呀。# 最后需要測試，檢驗代碼是否正常運行temp = string[i: i + substring_length]if temp == temp[::-1]:return tempsubstring_length -= 1print get_reverstring("abcdcbadegtefetge")

2. 中心搜索法

選取一個中心點index，按偶數和奇數兩種情況進行遍歷尋找，并將獲得的子字符串進行比較，返回最大子字符串。

參考：https://blog.csdn.net/weixin_41863544/article/details/110493234

class Solution(object):def center(self, left, right, s):step = []# 如果是奇數字符串if left == right:k = 1while left - k >= 0 and left + k < len(s):if s[left - k] == s[right + k]:step = s[left - k: right + k + 1]k += 1else:break# 如果是偶數字符串if left + 1 == right:k = 0while left - k >= 0 and right + k < len(s):if s[left - k] == s[right + k]:step = s[left - k: right + k + 1]k += 1else:breakreturn stepdef longestPalindrome(self, s):""":type s: str:rtype: str"""l = []for i in range(0, len(s) - 1):# 假設i為奇數字符串中心的情況，進行回文字符串判斷step1 = self.center(i, i, s)# 假設i為偶數字符串中心的情況，進行回文字符串判斷step2 = self.center(i, i + 1, s)if len(l) < max(len(step1), len(step2)):if len(step1) > len(step2):l = step1else:l = step2if l == []:return s[0]return ls = "cdeffeba" o = Solution() print(o.longestPalindrome(s)) # leetcode submit region end(Prohibit modification and deletion) # 可以將自定義的python函數封裝成一個類class Solution(object)，通過創建對象o = class_name()，對象調用類內創建的函數獲得運行結果o.longestPalindrome(s)

3. 中心擴展法

枚舉實現的耗時是我們無法忍受的。那么有沒有高效查找回文子串的方法呢？答案當然是肯定的，那就是中心擴展法，選擇一個元素作為中心，然后向外發散的尋找以該元素為圓心的最大回文子串。但是又出現了新的問題，回文子串的長度即可能是基數，也可能好是偶數，對于長度為偶數的回文子串來說是不存在中心元素的。那有什么方法解決中心擴展法中的偶數奇數、有中心無中心問題呢？

那是否有一種辦法能將奇偶長度的子串歸為一類，統一使用中心擴展法呢？它就是manacher算法，在原字符串中插入特殊字符，例如插入#后原字符串變成'#3#5#5#3#4#3#2#1#'。這樣無論原字符串長度是奇數還是偶數，擴展后的字符串長度都是奇數，所以只需要以index為中心向兩邊擴展判斷即可。

現在我們對新字符串使用中心擴展發即可，中心擴展法得到的不含中心點的半徑長度就是子串的長度。

參考：https://www.cnblogs.com/baiyb/p/8326216.html

• 中心擴展法～優化前

def get_max_substr(string):str_list = [s for s in string]center_string = '#' + '#'.join(str_list) + '#'# 以需要判斷的字符串中心為循環條件，每次循環操作對象：全部的數組 --> 雙循環max_range = 0max_substr = ''for index in range(0, len(center_string)):temp_range = 0# 以index為中心擴展的字符串半徑，最長是index，e.g. index =0, max_radius = 0; index = 1, max_radius = 1for r in range(1, index + 1):if index - r >= 0 and index + r <= len(center_string) - 1:print center_string[index - r], center_string[index + r]if center_string[index - r] == center_string[index + r]:temp_range = relse:breakelse:break# substr, substr_length = get_str_length(center_string, index)if temp_range > max_range:max_range = temp_rangemax_substr = center_string[index - max_range : index + max_range + 1].replace('#', '')return max_range, max_substrif __name__ == "__main__":string = "ecaacd"max_range, max_substr = get_max_substr(string)print max_range, max_substr

• 中心擴展法優化后

功能已經實現了，經過測試也沒有bug，但是我們靜下心來想一想，目前的解法是否還有優化空間呢？根據目前的解法，如果某個index3中心的最長回文子串長度比max_length要小，我們不必更新max_length。換句話說，我們計算以index3為中心的最長回文字串長度是做了無用功。

==> 優化：在遍歷一個新的元素時，我們要優先判斷它有沒有潛質能超越max_length，如果不能超過，就繼續遍歷下一個元素。

def get_max_substr(string):str_list = [s for s in string]center_string = '#' + '#'.join(str_list) + '#'# 以需要判斷的字符串中心為循環條件，每次循環操作對象：全部的數組 --> 雙循環max_range = 0max_substr = ''for index in range(0, len(center_string)):temp_range = 0# 以index為中心擴展的字符串半徑，最長是index，e.g. index =0, max_radius = 0; index = 1, max_radius = 1for r in range(max_range + 1, index + 1):# 以index為中心，r為半徑的子字符串長度是否在整體字符串范圍內-->優化：我覺得直接判斷index中心有沒有超過max_range的潛質if index - max(max_range, r) >= 0 and index + max(max_range, r) <= len(center_string) - 1:# 取子字符串時，注意排序str_l = center_string[index - 1:index - max_range - 1: -1]str_r = center_string[index + 1: index + max_range + 1]# print str_l, str_rif str_l == str_r:if center_string[index - r] == center_string[index + r]:temp_range = relse:breakelse:breakelse:breakif temp_range > max_range:max_range = temp_rangemax_substr = center_string[index - max_range: index + max_range + 1].replace('#', '')return max_range, max_substrif __name__ == "__main__":string = "ecaac"max_range, max_substr = get_max_substr(string)print max_range, max_substr

github地址

yuyongsheng1990:https://github.com/yuyongsheng1990/python_training/tree/master/training_001_Longest_Palindrome_String

總結

以上是生活随笔為你收集整理的python programming training(一)：最大回文子字符串的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。