清徐北京网站建设,国内 虚拟主机,wordpress 代码 工具,深圳做网站需要多少费用392.判断子序列
力扣题目链接(opens new window)
给定字符串 s 和 t #xff0c;判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些#xff08;也可以不删除#xff09;字符而不改变剩余字符相对位置形成的新字符串。#xff08;例如#xff0c;判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些也可以不删除字符而不改变剩余字符相对位置形成的新字符串。例如ace是abcde的一个子序列而aec不是。
示例 1
输入s abc, t ahbgdc输出true
示例 2
输入s axc, t ahbgdc输出false
提示
0 s.length 1000 t.length 10^4
两个字符串都只由小写字符组成。 双指针法
初始化两个指针i 用于遍历字符串 sj 用于遍历字符串 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, ahbgdcprint(isSubsequence(s1, t1)) # 应该输出 True
print(isSubsequence(s2, t2)) # 应该输出 False115.不同的子序列
力扣题目链接(opens new window)
给定一个字符串 s 和一个字符串 t 计算在 s 的子序列中 t 出现的个数。
字符串的一个 子序列 是指通过删除一些也可以不删除字符且不干扰剩余字符相对位置所组成的新字符串。例如ACE 是 ABCDE 的一个子序列而 AEC 不是
题目数据保证答案符合 32 位带符号整数范围。 提示
0 s.length, t.length 1000s 和 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)# 初始化一个 (m1) x (n1) 的 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
