代码随想录算法训练营第五十五天| LeetCode647. 回文子串、516.最长回文子序列

647. 回文子串

题目描述: 647. 回文子串.

解法

二维dp

class Solution(object):
    def countSubstrings(self, s):
        dp = [[False] * len(s) for _ in range(len(s))]
        count = 0
        for i in range(len(s)-1,-1,-1):
            for j in range(i,len(s)):
                if s[i] == s[j]:
                    if i == j or j-1 == i:
                        dp[i][j] = True
                        count += 1
                    else:
                        dp[i][j] = dp[i+1][j-1]
                        if dp[i][j]:
                            count += 1
        return count
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

d[i][j]是表示从i到j的子串是否是回文串，首先考虑i和j位置上的是否相等，不相等的话肯定不是回文串。相等的话还要看dp[i+1][j-1]是什么情况。

516.最长回文子序列

题目描述: 516.最长回文子序列.

解法

二维dp

class Solution(object):
    def longestPalindromeSubseq(self, s):
        dp = [[0] * len(s) for _ in range(len(s))]
        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] = j-i+1
                    else:
                        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

其实和回文子串思路是一样的，但是回文子序列没有那么多要求，如果两个都加进去不行的话，就考虑只加一个，而且要记住dp的含义，不要直接返回dp[-1][-1]