LC 115. 不同的子序列

题目描述

这是 LeetCode 上的 115. 不同的子序列 ，难度为困难。

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）

题目数据保证答案符合 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
    ^^^

提示：

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

基本思路

有两个字符串 s 和 t，长度数量级都为 $10^3$。

一个朴素的想法是，找出所有 s 的子序列，与 t 进行比较，找所有子序列的复杂度是 $O(2^n)$，肯定会超时。

因此，我们放弃这种朴素思路。

字符串匹配也不具有二段性质，不可能有 $log$ 级别的算法，那么复杂度再往下优化就是 $O(n * m)$ 的递推 DP 做法了。

动态规划

DP 的状态定义猜测通常是一门经验学科。

但是，对于两个字符串匹配，一个非常通用的状态定义如下：

定义 $f[i][j]$ 为考虑 s 中 $[0,i]$ 个字符，t 中 $[0,j]$ 个字符的匹配个数。

那么显然对于某个 $f[i][j]$ 而言，从「最后一步」的匹配进行分析，包含两类决策：

不让 s[i] 参与匹配，也就是需要让 s 中 $[0,i-1]$ 个字符去匹配 t 中的 $[0,j]$ 字符。此时匹配值为 $f[i-1][j]$
让 s[i] 参与匹配，这时候只需要让 s 中 $[0,i-1]$ 个字符去匹配 t 中的 $[0,j-1]$ 字符即可，同时满足 s[i]=t[j]。此时匹配值为 $f[i-1][j-1]$

最终 $f[i][j]$ 就是两者之和。

Java 代码：

class Solution {
    public int numDistinct(String s, String t) {
        // 技巧：往原字符头部插入空格，这样得到 char 数组是从 1 开始
        // 同时由于往头部插入相同的（不存在的）字符，不会对结果造成影响，而且可以使得 f[i][0] = 1，可以将 1 这个结果滚动下去
        int n = s.length(), m = t.length();
        s = " " + s;
        t = " " + t;
        char[] cs = s.toCharArray(), ct = t.toCharArray();
        // f(i,j) 代表考虑「s 中的下标为 0~i 字符」和「t 中下标为 0~j 字符」是否匹配
        int[][] f = new int[n + 1][m + 1];
        // 原字符只有小写字符，当往两个字符插入空格之后，f[i][0] = 1 是一个显而易见的初始化条件
        for (int i = 0; i <= n; i++) f[i][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                // 包含两种决策：
                // 不使用 cs[i] 进行匹配，则有 f[i][j] = f[i - 1][j]
                f[i][j] = f[i - 1][j];
                // 使用 cs[i] 进行匹配，则要求 cs[i] == ct[j]，然后有  f[i][j] += f[i - 1][j - 1]
                if (cs[i] == ct[j]) f[i][j] += f[i - 1][j - 1];
            }
        }
        return f[n][m];
    }
}

C++ 代码：

class Solution {
public:
    int numDistinct(string s, string t) {
        int n = s.length(), m = t.length();
        s = " " + s;
        t = " " + t;
        vector<vector<unsigned long long>> f(n + 1, vector<unsigned long long>(m + 1, 0));
        for (int i = 0; i <= n; i++) f[i][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                f[i][j] = f[i - 1][j];
                if (s[i] == t[j]) f[i][j] += f[i - 1][j - 1];
            }
        }
        return f[n][m];
    }
};

Python 代码：

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

TypeScript 代码：

function numDistinct(s: string, t: string): number {
    const n: number = s.length, m: number = t.length;
    const f: number[][] = new Array(n + 1).fill(0).map(() => new Array(m + 1).fill(0));
    for (let i: number = 0; i <= n; i++) f[i][0] = 1;
    for (let i: number = 1; i <= n; i++) {
        for (let j: number = 1; j <= m; j++) {
            f[i][j] = f[i - 1][j];
            if (s.charAt(i - 1) === t.charAt(j - 1)) f[i][j] += f[i - 1][j - 1];
        }
    }
    return f[n][m];
};

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

PS. 需要说明的是，由于中间结果会溢出，CPP 中必须使用 unsigned long long，而 Java 不用。由于 Java 中 int 的存储机制，只要在运算过程中只要不涉及取 min、取 max 或者其他比较操作的话，中间结果溢出不会影响最终结果。

总结

关于字符串匹配，通常有两种（你也可以理解为一种）通用的状态定义：

$f[i][j]$ 表示「第一个字符 s 中 $[0,i]$ 个字符」与「第二个字符 t 中 $[0,j]$ 个字符」的匹配结果
$f[i][j]$ 表示「第一个字符 s 中 $[0,i]$ 个字符」与「第二个字符 t 中 $[0,j]$ 个字符」且「最后一个字符为 t[j]」的匹配结果