判断子序列
题目链接
给定字符串 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
- 两个字符串都只由小写字符组成。
首先,我们定义一个二维布尔数组 dp,其中 dp[i][j] 表示字符串 t 的前 i 个字符是否包含字符串 s 的前 j 个字符作为子序列。我们的目标是求出 dp[t.length()][s.length()]。
动态规划的转移方程如下:
-
当 s[j] != t[i] 时,dp[i][j] = dp[i-1][j]。这表示如果当前考察的字符 t[i] 和 s[j] 不相等,那么 t 的前 i 个字符是否包含 s 的前 j 个字符作为子序列的结果与 t 的前 i-1 个字符是否包含 s 的前 j 个字符作为子序列的结果相同。
-
当 s[j] == t[i] 时,我们有两种选择:
- 我们可以选择使用 t[i] 来匹配 s[j],此时我们需要查看 t 的前 i-1 个字符是否包含 s 的前 j-1 个字符作为子序列,这就是 dp[i-1][j-1]。
- 我们也可以选择不使用 t[i] 来匹配 s[j],即我们跳过 t[i],查看 t 的前 i-1 个字符是否包含 s 的前 j 个字符作为子序列,这就是 dp[i-1][j]。
因此,当 s[j] == t[i] 时,dp[i][j] = dp[i-1][j-1] || dp[i-1][j]。如果 t 的前 i-1 个字符包含 s 的前 j-1 个字符作为子序列,或者 t 的前 i-1 个字符包含 s 的前 j 个字符作为子序列,那么 t 的前 i 个字符就包含 s 的前 j 个字符作为子序列。文章来源:https://www.toymoban.com/news/detail-604846.html
下面是使用 Python 实现的代码:文章来源地址https://www.toymoban.com/news/detail-604846.html
def isSubsequence(s, t):
m, n = len(t), len(s)
dp = [[False] * (n + 1) for _ in range(m + 1)]
# 当 s 为空字符串时,它是任何字符串的子序列
for i in range(m + 1):
dp[i][0] = True
for i in range(1, m + 1):
for j in range(1, min(i + 1, n + 1)): # j 不能大于 i
if t[i - 1] == s[j - 1]:
dp[i][j] = dp[i - 1][j - 1] or dp[i - 1][j]
else:
dp[i][j] = dp[i - 1][j]
return dp[m][n]
到了这里,关于每日一题之判断子序列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!