代码随想录算法训练营Day 54 || 392.判断子序列、115.不同的子序列
392.判断子序列
力扣题目链接(opens new window)
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
示例 1：
- 输入：s = "abc", t = "ahbgdc"
- 输出：true
示例 2：
- 输入：s = "axc", t = "ahbgdc"
- 输出：false
提示：
- 0 <= s.length <= 100
- 0 <= t.length <= 10^4
两个字符串都只由小写字符组成。
双指针法
- 初始化两个指针：
i用于遍历字符串s，j用于遍历字符串t。 - 遍历字符串
t：使用指针j遍历字符串t，对于t中的每个字符，检查是否与s中的当前字符（由i指向）相匹配。 - 匹配字符：如果匹配（即
s[i] == t[j]），则将i和j同时向前移动；如果不匹配，则只将j向前移动。 - 检查是否遍历完
s：如果i等于s的长度，说明s是t的子序列；如果j先达到t的末尾，则说明s不是t的子序列。
def isSubsequence(s: str, t: str) -> bool:i, j = 0, 0while i < len(s) and j < len(t):if s[i] == t[j]:i += 1j += 1return i == len(s)# 测试代码
s1, t1 = "abc", "ahbgdc"
s2, t2 = "axc", "ahbgdc"print(isSubsequence(s1, t1)) # 应该输出 True
print(isSubsequence(s2, t2)) # 应该输出 False
115.不同的子序列
力扣题目链接(opens new window)
给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。
字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）
题目数据保证答案符合 32 位带符号整数范围。
提示：
- 0 <= s.length, t.length <= 1000
- s 和 t 由英文字母组成
动态规划思路解析
-
状态定义：
dp[i][j]表示考虑s的前i个字符和t的前j个字符时，t作为s的子序列出现的次数。
-
状态初始化：
dp[0][0] = 1：两个空字符串匹配的次数是1。dp[i][0] = 1对所有i：如果t是空字符串，那么无论s是什么，都只有一种方式使t成为s的子序列（即全部删除s）。
-
状态转移：
- 如果
s的第i个字符与t的第j个字符相同（s[i - 1] == t[j - 1]），那么t的前j个字符可以在s的前i - 1个字符中找到对应的子序列，加上当前匹配的字符，形成新的子序列。同时，t的前j个字符也可能在s的前i - 1个字符中出现多次，不包括s[i]。因此，dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]。 - 如果不同（
s[i - 1] != t[j - 1]），则s的第i个字符不能用于匹配t的第j个字符。这时，dp[i][j] = dp[i - 1][j]。
- 如果
-
最终结果：
dp[len(s)][len(t)]是最终结果，表示s的前len(s)个字符中t的前len(t)个字符作为子序列出现的总次数。
def numDistinct(s: str, t: str) -> int:m, n = len(s), len(t)# 初始化一个 (m+1) x (n+1) 的 dp 矩阵dp = [[0] * (n + 1) for _ in range(m + 1)]# 当 t 为空字符串时，s 的子序列中总有一种方式使得 t 为其子序列for i in range(m + 1):dp[i][0] = 1# 填充 dp 矩阵for i in range(1, m + 1):for j in range(1, n + 1):if s[i - 1] == t[j - 1]:# 如果字符匹配，可以选择使用或不使用 s[i-1]dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]else:# 如果字符不匹配，只能选择不使用 s[i-1]dp[i][j] = dp[i - 1][j]return dp[m][n]# 测试代码
s = "babgbag"
t = "bag"
print(numDistinct(s, t)) # 应该输出 5