代码随想录算法训练营Day 56| 动态规划part17 | 647. 回文子串、5. 最长回文子串、516.最长回文子序列

代码随想录算法训练营Day 56| 动态规划part17 | 647. 回文子串、5. 最长回文子串、516.最长回文子序列

---

---

647. 回文子串

题目链接

一、法一

class Solution(object):
    def countSubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """
        #布尔类型的dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。
        dp=[[False]*len(s) for _ in range(len(s))]
        res=0
        for i in range(len(s)-1,-1,-1):
            for j in range(i,len(s)):
                if s[i]==s[j]:
                    if j-i<=1:
                        res +=1
                        dp[i][j]=True
                    elif dp[i+1][j-1]:
                        res +=1
                        dp[i][j]=True
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

---

5. 最长回文子串

题目链接

一、动态规划

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        # 同回文子串的思路，增加了判断长度的逻辑
        dp=[[False]*len(s) for _ in range(len(s))]
        maxlength=0
        left=0
        right=0
        for i in range(len(s)-1,-1,-1):
            for j in range(i,len(s)):
                if s[i]==s[j]:
                    if j-i<=1:
                        dp[i][j]=True
                    elif dp[i+1][j-1]:
                        dp[i][j]=True
                if dp[i][j] and j-i+1>maxlength:
                    maxlength=j-i+1
                    left=i
                    right=j
        return s[left:right+1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

---

516.最长回文子序列

题目链接

一、法一

class Solution(object):
    def longestPalindromeSubseq(self, s):
        """
        :type s: str
        :rtype: int
        """
        # dp[i][j]:表示s[i:j]中的最长回文子序列长度
        dp=[[0]*len(s) for _ in range(len(s))]
        # 首先要考虑当i 和j 相同的情况，从递推公式：dp[i][j] = dp[i + 1][j - 1] + 2; 可以看出 递推公式是计算不到 i 和j相同时候的情况。所以手动初始化对角线
        for i in range(len(s)):
            dp[i][i]=1
        for i in range(len(s)-1,-1,-1):
            for j in range(i+1,len(s)):
                if s[i]==s[j]:
                    dp[i][j]=dp[i+1][j-1]+2
                else:
                    dp[i][j]=max(dp[i+1][j],dp[i][j-1])
        return dp[0][-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18