Python最长回文子串
1.暴力解法(Brute Method)
暴力求解是最容易想到的，要截取字符串的所有子串，然后再判断这些子串中哪些是回文的，最后返回回文子串中最长的即可。
这里我们可以使用两个变量，一个记录最长回文子串开始的位置，一个记录最长回文子串的长度，最后再截取。
1 2 3 | class Solution: def longestPalindrome(self, s): if (len(s) |
2.中心扩散法
从左向右遍历：选择一个中心点向两侧扩展，分别考虑奇数组合偶数组的情况。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | 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 |
3.动态规划
思路与算法
对于一个子串而言，如果它是回文串，并且长度大于 22，那么将它首尾的两个字母去除之后，它仍然是个回文串。例如对于字符串 “ababa”，如果我们已经知道 “bab” 是回文串，那么 “ababa” 一定是回文串，这是因为它的首尾两个字母都是 “a”。
注意：在状态转移方程中，我们是从长度较短的字符串向长度较长的字符串进行转移的，因此一定要注意动态规划的循环顺序。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | class Solution: def longestPalindrome(self, s): n = len(s) if n = n: break if s[i] != s[j]: dp[i][j] = False else: if j - i 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 仅由数字和英文字母（大写和/或小写）组成
解题思路
中心扩展法：
把每个字母（或者数字）当成回文串的中心，这里要考虑两种情况，回文串的长度为奇数或者偶数情况。
从每一个位置出发，向两边扩散即可。传递下去的条件是s[L]==s[R]；
遇到不是回文的时候结束。
eg: str = “acdbbdaa”。需要寻找从第一个b（位置为3）出发最长回文串为多少。
寻找方法：
首先往左寻找与当期位置相同的字符，直到遇到不相等为止。
然后往右寻找与当期位置相同的字符，直到遇到不相等为止。
最后左右双向扩散，直到左和右不相等。
代码
1 2 3 4 5 6 7 8 9 10 11 | 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 |
因为我们最后要返回的是具体子串，而不是长度，因此，还需要记录一下maxLen时的起始位置（maxStart），即此时还要maxStart=len
大佬的代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | class Solution: def longestPalindrome(self, s: str) -> str: n = len(s) if n str: while 0 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 |
以上为个人经验，希望能给大家一个参考，也希望大家多多支持IT俱乐部。
