2816. 判断子序列

**判断子序列**

在计算机科学中，子序列是指一个序列的连续子集。例如，如果我们有一个序列 `abc`,那么它的子序列包括 `a`, `b`, `c`, `ab`, `bc` 和 `abc`。

在本文中，我们将讨论如何判断一个给定的序列是否是另一个序列的子序列。这是一个非常重要的问题，因为它有很多实际应用，例如文本匹配、模式识别等。

**问题描述**

给定两个字符串 `s` 和 `t`，我们需要判断 `t` 是否是 `s` 的子序列。如果 `t` 是 `s` 的子序列，我们返回 `True`，否则返回 `False`。

**解决方案**

这个问题可以使用动态规划来解决。动态规划是一种非常有效的算法，它通过分解一个大问题成多个小问题来解决。

我们首先定义一个二维数组 `dp`，其中 `dp[i][j]` 表示 `s` 的前 `i` 个字符和 `t` 的前 `j` 个字符是否能匹配。我们初始化 `dp[0][0] = True`，因为空字符串是任何字符串的子序列。

然后，我们遍历 `s` 和 `t` 的所有可能的前缀，并更新 `dp[i][j]` 的值。如果 `s` 的第 `i` 个字符等于 `t` 的第 `j` 个字符，我们就设置 `dp[i][j] = dp[i-1][j-1]`，因为这两个字符串匹配了。

如果 `s` 的第 `i` 个字符不等于 `t` 的第 `j` 个字符，我们就设置 `dp[i][j] = dp[i-1][j]`，因为我们可以忽略 `s` 的第 `i` 个字符。

最后，我们返回 `dp[len(s)][len(t)]`，因为这就是我们的答案。

**代码示例**

def is_subsequence(s, t):
 """
 判断 s 是否是 t 的子序列。
 Args:
 s (str): 序列1。
 t (str): 序列2。
 Returns:
 bool: True 如果 s 是 t 的子序列，False 否则。
 """
 m, n = len(s), len(t)
 dp = [[False] * (n +1) for _ in range(m +1)]
 # 初始化 dp[0][0] = True # 遍历 s 和 t 的所有可能的前缀 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]
 else:
 dp[i][j] = dp[i -1][j]
 return dp[m][n]

# 测试s = "abc"
t = "ahbgdc"
print(is_subsequence(s, t)) # Trues = "axc"
t = "ahbgdc"
print(is_subsequence(s, t)) # False