动态规划（最长回文子串）

95 阅读 0 评论 63 点赞

我是靠谱客的博主幽默百褶裙，这篇文章主要介绍动态规划（最长回文子串），现在分享给大家，希望可以做个参考。

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

递推公式：dp[left][right]=s.charAt(left)==s.charAt(right)&&dp[left+1][right-1]

暴力枚举：

建立动态规划2维数组。从小到大判断字符串大小。

PS:需满足2个条件，一个是左右相同，第二是left+1，right-1是True。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def longestPalindrome(self, s: str) -> str:
        L=len(s)
        if len==1:
            return s
        if len(s)==2:
            if s[0]==s[1]:
                return s
            else:
                return s[0]
        t=[[False for s in range(L) ] for _ in range(L)]
        for i in range(3):
            for n in range(L-i):
                if s[n]==s[n+i] :
                    t[n][n+i]=True
                    re = s[n:n + i + 1]
                    max=i
        for i in range(3,L):
            for n in range(L-i):
                if s[n]==s[n+i] and t[n+1][n+i-1]:
                    t[n][n+i]=True
                    re=s[n:n+i+1]
                    max=i
        return re