如何经过Python快速定位最长的回文子串

本篇内容介绍了“如何通过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[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.中心扩散法

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

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[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.动态规划

思路与算法

对于一个子串而言，如果它是回文串，并且长度大于 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[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):

            # 枚举左边界，左边界的上限设置可以宽松一些

            for i in range(n):

                # 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得

                j = L + i - 1

                # 如果右边界越界，就可以退出当前循环

                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,就被认为是回文串，跳入下一个环节

                # 只要 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 仅由数字和英文字母（大写和/或小写）组成

解题思路

中心扩展法：

把每个字母（或者数字）当成回文串的中心，这里要考虑两种情况，回文串的长度为奇数或者偶数情况。

从每一个位置出发，向两边扩散即可。传递下去的条件是s[L]==s[R]；

遇到不是回文的时候结束。

eg: str = “acdbbdaa”。需要寻找从第一个b（位置为3）出发最长回文串为多少。

寻找方法：

首先往左寻找与当期位置相同的字符，直到遇到不相等为止。

然后往右寻找与当期位置相同的字符，直到遇到不相等为止。

最后左右双向扩散，直到左和右不相等。

代码

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):    #若长度为奇数的长

                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

“如何通过Python快速定位最长的回文子串”的内容就介绍到这里了，感谢大家的阅读。

（编辑：银川站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!