研习代码 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 <= 100
• 0 <= 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 <= 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）过程想法

        递推关系的式子着实是没想到，，，

        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]