研习代码 day47 | 动态规划——子序列问题3
一、判断子序列
1.1 题目
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
进阶：
如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
示例 1：
输入：s = "abc", t = "ahbgdc" 输出：true
示例 2：
输入：s = "axc", t = "ahbgdc" 输出：false
提示：
0 <= s.length <= 1000 <= t.length <= 10^4- 两个字符串都只由小写字符组成。
1.2 题目链接
392.判断子序列
1.3 解题思路和过程想法
（1）解题思路
双指针遍历：用两个指针分别遍历两个字符串，若是两指针所指相同，则两指针同时往后；否则，将指向“母字符串”的指针向后移动；最后判断指向“子字符串”的指针是否到达其串后侧位置
动态规划：用两层循环结构对比两字符串的元素，外层遍历“子串”，内层遍历“母串”。若是两指针所指的前一元素相同——s[i-1] == t[j-1]，则更新“以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度dp[i][j]” ——dp[i][j] = dp[i-1][j-1]+1；若是二者不相等，则dp[i][j]等于前值，不做更新——dp[i][j] = dp[i][j-1]；最后判断dp[len(s)][len(t)]==lens(s)即可。
（2）过程想法
一题多解才能融会贯通所学的知识
1.4 代码
1.4.1 双指针遍历
class Solution:def isSubsequence(self, s: str, t: str) -> bool:# 利用双指针分别指向两个字符串point_s , point_t = 0, 0# 遍历字符串 t while point_s < len(s) and point_t < len(t):# 若匹配，则两指针都向后移一位if s[point_s] == t[point_t]:point_s += 1# 否则，只有指针 t 向后移point_t += 1# 若指针 s 到达最后，则表明匹配成功return point_s == len(s)1.4.2 动态规划
class Solution:def isSubsequence(self, s: str, t: str) -> bool:m,n = len(s),len(t)dp = [[0] * (n+1) for _ in range(m+1)]for i in range(1, m+1):for j in range(1, n+1):if s[i-1] == t[j-1]:dp[i][j] = dp[i-1][j-1] + 1else:dp[i][j] = dp[i][j-1]if dp[m][n] == m:return Trueelse:return False二、不同的子序列
1.1 题目
给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。
示例 1：
输入：s = "rabbbit", t = "rabbit" 输出：3 解释： 如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。rabbbitrabbbitrabbbit
示例 2：
输入：s = "babgbag", t = "bag" 输出：5 解释： 如下所示, 有 5 种可以从 s 中得到 "bag" 的方案。babgbagbabgbagbabgbagbabgbagbabgbag
提示：
1 <= s.length, t.length <= 1000s和t由英文字母组成
1.2 题目链接
115.不同的子序列
1.3 解题思路和过程想法
（1）解题思路
当前的匹配情况会受到之前元素的情况所影响，且影响的方式是类似的，考虑采用动态规划的策略。数组：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]
递推关系：若二者元素相匹配，当前情况取决于 用或不用 当前的元素，
dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
若二者元素不匹配，当前情况的结果与不用当前元素的情况相同
dp[i][j] = dp[i-1][j]
图片来源：代码随想录，红色文字是自己加的
初始化：由上述递推关系可知当前位置的填写是基于左上方和正上方的元素，所以需要提前对首行首列进行初始赋值
# 首行：没有母串，直接赋值 0
dp[0][j] = 0
# 首列：没有子串，即空子串，赋值1
dp[i][0] = 1
（2）过程想法
递推关系的式子着实是没想到，，，
1.4 代码
class Solution:def numDistinct(self, s: str, t: str) -> int:long,short = len(s),len(t)# 以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]# 以母串位置为行坐标，以子串位置为列坐标dp = [[0]*(short+1) for _ in range(long+1)]# 递推关系：若二者元素相匹配，当前情况取决于 用或不用 当前的元素# 若匹配，则dp[i][j] = dp[i-1][j-1] + dp[i-1][j]# 初始化：由上述递推关系可知当前位置的填写是基于左上方和正上方的元素，所以需要提前对首行首列进行初始赋值for j in range(short+1): # 首行：没有母串，直接赋值 0dp[0][j] = 0for i in range(long+1): # 首列：没有子串，即空子串，赋值1dp[i][0] = 1for i in range(1,long+1):for j in range(1,short+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[long][short]