代码随想录算法训练营第四十七天|392.判断子序列，115.不同的子序列

作者：盐析白兔 | 2024-07-29 22:17:06

踩

系列文章目录

文章目录

系列文章目录
392.判断子序列
115.不同的子序列

392.判断子序列

题目链接： 392.判断子序列
题目内容： 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
视频讲解： 动态规划，用相似思路解决复杂问题 | LeetCode：392.判断子序列

动态规划问题的五步曲：

确定dp数组（dp table）以及下标的含义：dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]
确定递推公式：
- if (s[i - 1] == t[j - 1])，那么dp[i][j] = dp[i - 1][j - 1] + 1;
- if (s[i - 1] != t[j - 1])，则dp[i][j] = dp[i][j - 1];
dp数组如何初始化：统一初始为0
确定遍历顺序：从左到右遍历，从上到下遍历
举例推导dp数组

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        dp=[[0]*(len(t)+1) for _ in range(len(s)+1)]
        for i in range(1,len(s)+1):
            for j in range(1,len(t)+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]
        if dp[-1][-1]==len(s):
            return True
        return False
1
2
3
4
5
6
7
8
9
10
11
12

115.不同的子序列

题目链接： 115.不同的子序列
题目内容： 给你两个字符串 s 和 t ，统计并返回在 s 的子序列中 t 出现的个数，结果需要对 109 + 7 取模。
视频讲解： 动态规划之子序列，为了编辑距离做铺垫 | LeetCode：115.不同的子序列

动态规划问题的五步曲：

确定dp数组（dp table）以及下标的含义：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]
确定递推公式：
- if (s[i - 1] == t[j - 1])，dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
- if (s[i - 1] != t[j - 1])，dp[i][j] = dp[i - 1][j]
dp数组如何初始化：dp[i][0] = 1，dp[0][j] = 0，其中dp[0][0]=1
确定遍历顺序：从左到右遍历，从上到下遍历
举例推导dp数组

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        dp=[[0]*(len(t)+1) for _ in range (len(s)+1)]
        for i in range(len(s)):
            dp[i][0]=1
        for j in range(1,len(t)):
            dp[0][j]=0
        for i in range(1,len(s)+1):
            for j in range(1,len(t)+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[-1][-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/盐析白兔/article/detail/900840