最长回文子串(动态规划)

2023-12-22 17:09:38

给你一个字符串?s,找到?s?中最长的回文子串。

如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。

示例 1:

输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。

示例 2:

输入:s = "cbbd"
输出:"bb"
class Solution:
    def longestPalindrome(self, s: str) -> str:
        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[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]



文章来源:https://blog.csdn.net/xiaoyang01234/article/details/135154413
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。