题目描述
给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。
一个字符串的子序列是指，通过删除一些（也可以不删除）字符而不改变剩余字符的相对位置形成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）。
示例：
输入：s = “rabbbit”, t = “rabbit”
输出：3
解释：有 3 种方法可以生成 “rabbit” 的子序列。
难度分析
这道题目是一个动态规划问题，属于中等偏上难度。
解题算法
方法一：动态规划
解题步骤
- 初始化一个
(m+1)x(n+1)的二维数组dp，其中m和n分别是字符串s和t的长度。dp[i][j]表示s的前i个字符中包含t的前j个字符的子序列个数。 - 设定初始条件：当
j=0，即t为空字符串时，dp[i][0]都为1。 - 遍历字符串
s和t，更新dp表：
- 如果
s[i-1] == t[j-1]，则dp[i][j] = dp[i-1][j-1] + dp[i-1][j]； - 否则，
dp[i][j] = dp[i-1][j]。
- 返回
dp[m][n]。
Python 示例
def numDistinct(s: str, t: str) -> int: m, n = len(s), len(t) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(m + 1): dp[i][0] = 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] + dp[i - 1][j] else: dp[i][j] = dp[i - 1][j] return dp[m][n]
方法二：记忆化递归（优化的 DFS）
解题步骤
- 使用递归函数
dfs(i, j)来表示从s[i:]和t[j:]开始的子序列匹配个数。 - 如果
j == len(t)，表示t已经被完全匹配，返回1。 - 如果
i == len(s)而j != len(t)，则无法匹配，返回0。 - 使用一个记忆化数组
memo来存储已计算的结果，避免重复计算。 - 递归计算两种情况：选择当前
s[i]或者跳过当前s[i]。
Python 示例
def numDistinct(s: str, t: str) -> int: memo = {} def dfs(i, j): if j == len(t): return 1 if i == len(s): return 0 if (i, j) in memo: return memo[(i, j)] if s[i] == t[j]: memo[(i, j)] = dfs(i + 1, j + 1) + dfs(i + 1, j) else: memo[(i, j)] = dfs(i + 1, j) return memo[(i, j)] return dfs(0, 0)
方法三：滚动数组优化的动态规划
Python 示例
def numDistinct(s: str, t: str) -> int: m, n = len(s), len(t) dp = [0] * (n + 1) dp[0] = 1 # 初始化dp数组，任何字符串都包含空字符串的子序列，即空序列本身 for i in range(1, m + 1): # 从后向前遍历，防止覆盖需要的数据 for j in range(n, 0, -1): if s[i - 1] == t[j - 1]: dp[j] += dp[j - 1] return dp[n]
算法分析
滚动数组技术可以减少动态规划的空间复杂度，只使用一维数组存储中间结果，大大减少了内存的使用。
方法四：空间优化的记忆化递归
解题步骤
- 类似于记忆化递归，使用一个一维数组
memo来代替二维数组，减少空间复杂度。 - 根据
t的长度来初始化memo。 - 使用递归方式填充
memo，每次计算后存储结果。
Python 示例
def numDistinct(s: str, t: str) -> int: n = len(t) memo = [-1] * (n + 1) def dfs(i, j): if j == n: return 1 if i == len(s): return 0 if memo[j] != -1: return memo[j] res = 0 if s[i] == t[j]: res = dfs(i + 1, j + 1) res += dfs(i + 1, j) memo[j] = res return res return dfs(0, 0)
总结
- 动态规划是解决此类问题的最直接方法，其时间和空间复杂度均较高。
- 记忆化递归提供了更灵活的解决方案，适用于解决复杂递归问题，但可能会导致堆栈溢出。
- 滚动数组和空间优化的递归可以显著减少空间复杂度，适用于空间敏感的应用。
应用示例
在文本分析和自然语言处理中，计算字符串的子序列可以帮助理解文本的结构和语义。例如，在关键词匹配、信息检索和语言模型中，这些技术可以用来计算和优化大量文本数据。
欢迎关注微信公众号 数据分析螺丝钉
