What is the main pattern behind the Distinct Subsequences problem?

It follows state transition dynamic programming where dp[i][j] counts ways to form t[0..j-1] from s[0..i-1].

Can this problem be solved without dynamic programming?

Recursive solutions exist but are inefficient due to overlapping subproblems; DP ensures polynomial time.

How do you handle empty target strings?

An empty target t is a subsequence of any prefix of s, so dp[i][0] = 1 for all i.

Is space optimization important here?

Yes, using a 1D array reduces space from O(n*m) to O(m) while preserving correct counts.

What common mistakes should be avoided?

Misaligned indices, forgetting base cases, and overwriting previous dp values during optimization are frequent errors.

#115

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

不同的子序列

给你两个字符串 s 和 t ，统计并返回在 s 的子序列中 t 出现的个数。测试用例保证结果在 32 位有符号整数范围内。示例 1：输入： s = "rabbbit", t = "rabbit" 输出： 3 解释：如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。 …

字符串动态规划

题目描述

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数。

测试用例保证结果在 32 位有符号整数范围内。

示例 1：

输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit

示例 2：

输入：s = "babgbag", t = "bag"
输出：5
解释：
如下所示, 有 5 种可以从 s 中得到 "bag" 的方案。 
babgbag
babgbag
babgbag
babgbag
babgbag

提示：

1 <= s.length, t.length <= 1000
s 和 t 由英文字母组成

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i][j]$ 表示字符串 $s$ 的前 $i$ 个字符中，子序列构成字符串 $t$ 的前 $j$ 个字符的方案数。初始时 $f[i][0]=1$ ，其中 $i \in [0,m]$ 。

当 $i \gt 0$ 时，考虑 $f[i][j]$ 的计算：

当 $s[i-1] \ne t[j-1]$ 时，不能选取 $s[i-1]$ ，因此 $f[i][j]=f[i-1][j]$ ；
否则，可以选取 $s[i-1]$ ，此时 $f[i][j]=f[i-1][j-1]$ 。

因此我们有如下的状态转移方程：

f[i][j]=\left\{ \begin{aligned} &f[i-1][j], &s[i-1] \ne t[j-1] \\ &f[i-1][j-1]+f[i-1][j], &s[i-1]=t[j-1] \end{aligned} \right.

最终的答案即为 $f[m][n]$ ，其中 $m$ 和 $n$ 分别是字符串 $s$ 和 $t$ 的长度。

时间复杂度 $O(m \times n)$ ，空间复杂度 $O(m \times n)$ 。

我们注意到 $f[i][j]$ 的计算只和 $f[i-1][..]$ 有关，因此，我们可以优化掉第一维，这样空间复杂度可以降低到 $O(n)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        m, n = len(s), len(t)
        f = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m + 1):
            f[i][0] = 1
        for i, a in enumerate(s, 1):
            for j, b in enumerate(t, 1):
                f[i][j] = f[i - 1][j]
                if a == b:
                    f[i][j] += f[i - 1][j - 1]
        return f[m][n]

speed

复杂度分析

指标	值
时间	complexity is O(n _m) for strings of lengths n and m, as each dp cell is computed once. Space complexity is O(m) with optimization, otherwise O(n_ m). Performance depends on careful DP state updates to avoid overcounting.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check if the candidate identifies dp[i][j] meaning and proper initialization.
question_mark
Watch if they correctly implement the state transition without skipping edge cases.
question_mark
Notice if they attempt space optimization or remain with full 2D table.

warning

常见陷阱

外企场景

error
Confusing character positions and misaligning indices in the dp table.
error
Forgetting to initialize dp[i][0] = 1, which causes incorrect counts for empty target subsequences.
error
Overwriting previous dp values during optimization, leading to undercounting.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute subsequences modulo a large prime to prevent integer overflow.
arrow_right_alt
Count distinct subsequences that match t but allow at most k skipped characters in between.
arrow_right_alt
Find the minimum-length subsequence in s that can generate t multiple times.

help

常见问题

外企场景

继续练习

#131 分割回文串 #132 分割回文串 II #97 交错字符串