[数据结构与算法]D55|子序列Part3

392.判断子序列

1.题目
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

2.实现
尝试用dp的方法做一下~

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        # 双指针法O(n)
        # n, m = len(s), len(t)
        # l = -1
        # res = True
        # for i in range(n):
        #     res = False
        #     for j in range(l + 1, m):
        #         if t[j] == s[i]:
        #             l = j
        #             res = True
        #             break
        #     if not res:
        #         return res
        # return res

        # dp[i][j]表示0 - i-1 s字符串 和 0 - j-1 t字符串 的公共子序列的长度
        n, m = len(s), len(t)
        dp = [[0] * (m + 1) for _ in range(n + 1)]
        for i in range(1, n+1):
            for j in range(1, m+1):
                if s[i - 1] == t[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = dp[i][j - 1]
        return dp[n][m] == n

115.不同的子序列

1.题目
给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。
字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，“ACE” 是 “ABCDE” 的一个子序列，而 “AEC” 不是）

2.实现
困难点：
1）递推公式有难度，设了dp后很难直观推导递推公式，下次要不自己写个3*3的表
2）看了题目后卡了很久dp的定义，纠结为啥要定义为0 - i-1的字符串内

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        n, m = len(s), len(t)
        # dp[i][j]表示0 - i-1 s字符串中 0 - j-1 t字符串的出现的个数
        # 此时dp[0][0]表示空字符串s 的 空字符串t出现1次
        dp = [[0]*(m + 1) for _ in range(n + 1)]
        for i in range(n + 1):
            dp[i][0] = 1
        for i in range(1, n + 1):
            for j in range(1, m + 1):
                if s[i - 1] == t[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
                else:
                    dp[i][j] = dp[i - 1][j]
        return dp[n][m]

小结
1.子序列的dp[i][]定义：
1）以nums[i - 1]结尾
2）0 - i-1的字符串
2.dp初始化：
据上述dp定义，此时特别关注dp[i][0] 和 dp[0][j]，此时可理解为字符串为空字符串，根据空字符串或者递推公式考虑如何初始化
3.递推公式：
如无思路建议画个表！！！

文章讲解