最长回文子串

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1:

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2:

输入: "cbbd"
输出: "bb"

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-palindromic-substring

根据题意:我们最先可以想到的方法是暴力法,设置两个指针从一头一尾向中间找,一旦找到符合条件的便退出得到结果。代码如下:

class Solution:
    def longestPalindrome(self, s: str) -> str:
        max_length = 1000
        left = 0
        right = len(s)
        @lru_cache()
        def dp(l, r):
            if l >= r:
                return ""
            if s[l:r+1] == s[l:r+1][::-1]:
                return s[l:r+1] 
            return dp(l+1, r) if len(dp(l+1, r)) >= len(dp(l, r-1)) else dp(l, r-1)
        return dp(left, right)

    使用暴力算法解决该题会超时,因此我们应该从别的方面入手,对于回文字符串来说,当我们去掉一头一尾(不考虑边界情况), 它仍然是一个回文字符串。如果它的字串s[i+1][j-1]是回文字符串,那么当头尾s[i] == s[j]相等的时候,则该字符串也是回文字符串。
现在来考虑一下边界情况,j > i是一定的,j - i + 1可以表示子串的长度,也就是说当子串 j - 1 - (i + 1) + 1 < 2的时候必为回文字符串(就一个字符)--> j - i < 3。
我们可以推出其状态方程 dp[i][j] = (dp[i+1][j-1]  and s[i] == s[j]) or j - i < 3。
对于dp的初始化,当i = j 时都为True,其它均为False。
每次得到的结果,我们将其与maxLen做比较,如果比maxLen大则记录其起始位置begin。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        size = len(s)
        if size < 2:
            return s
        dp = [[False for _ in range(size)] for _ in range(size)]
        maxLen = 1
        begin = 0
        for i in range(size):
            dp[i][i] = True
        for j in range(1, size):
            for i in range(0, j):
                if s[i] == s[j]:
                    if j - i < 3:
                        dp[i][j] = True
                    else:
                        dp[i][j] = dp[i + 1][j - 1]
                else:
                    dp[i][j] = False
                if dp[i][j]:
                    cur_len = j - i + 1
                    if maxLen < cur_len:
                        maxLen = cur_len
                        begin = i
        return s[begin:begin + maxLen]
点赞

发表评论

Title - Artist
0:00