一、判断子序列
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）过程想法文章来源：https://www.toymoban.com/news/detail-764326.html
一题多解才能融会贯通所学的知识
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] + 1
else:
dp[i][j] = dp[i][j-1]
if dp[m][n] == m:
return True
else:
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 <= 1000-
s和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）过程想法
递推关系的式子着实是没想到，，，文章来源地址https://www.toymoban.com/news/detail-764326.html
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): # 首行：没有母串，直接赋值 0
dp[0][j] = 0
for i in range(long+1): # 首列：没有子串，即空子串，赋值1
dp[i][0] = 1
for 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]到了这里，关于研习代码 day47 | 动态规划——子序列问题3的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
