LeetCode题目115:不同子序列

题目描述

给定一个字符串 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)