LeetCode | 115 不同的子序列

题目地址:https://leetcode-cn.com/problems/distinct-subsequences/description/
给定一个字符串 和一个字符串 T,计算在 S 的子序列中 T 出现的个数。

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

比如:S = "rabbbit", T = "rabbit",则输出 3

思路一

最简单直接的思路就是暴力枚举 S 的所有子序列,然后逐一比较,时间复杂度为 $O(2^n)$,显然是不可接受的。

思路二

一个比较容易想到的思路是递归求解,先在 S 中找到 T 的第一个字符,然后每找到一个就从 S 的下一个位置开始递归找 T 的下一个字符,递归的边界条件就是 T 的下标为 T 的长度,这时候说明找到了一个子序列,返回 1,然后将结果累加即可。代码如下:

函数中 s_it_i 表示从 s 的下标为 s_i 的地方开始查找 t 下标为 t_i 的字符,初始调用即为 work(s, t, 0, 0)

vector<vector<int>> cache;
int numDistinctR(string & s, string & t, size_t s_i, size_t t_i) {
    if (t_i == t.size()) return 1;
    int sum = 0;
    for (int i = s_i; i < s.size(); ++i) {
        if (s[i] == t[t_i]) {
            if (cache[i + 1][t_i + 1] >= 0) sum += cache[i + 1][t_i + 1]; 
            else sum += work(s, t, i + 1, t_i + 1);
        }
    }
    cache[s_i][t_i] = sum;
    return sum;
}

由于直接递归会有大量重复计算,同样会超时,这里使用一个简单的优化技巧就是使用缓存,或者叫备忘录,来记录那些已经计算过的值。递归的办法比较容易想到,但效率不高,而且有可能发生栈溢出,这段代码的耗时为 16ms

思路三

通常这种递归是有可能通过动态规划来解决的,这道题也确实可以通过动态规划解决,那么我们应该怎么使用动态规划来求解这道题呢?首先我们要定义状态,我们可以定义 dp[i][j]s 中前 j 个字符组成的字符串子序列为 t 中前 i 个字符的个数。无论 t[i - 1] 是否等于 s[j - 1]s 多加上来一个字符是不影响原来的 dp[i][j - 1] 的,而如果加上来这个刚好跟 t 对应的字符相等,就会多出来 dp[i - 1][j - 1] 个子序列,所以我们就可以得到 dp[i][j] = dp[i][j - 1] + t[i - 1] == s[j - 1] ? dp[i - 1][j - 1] : 0 的递推关系。

动态规划还有一个需要思考的地方就是初始条件。很显然,dp[0][·] 也就是 t 为空的时候,子序列的个数永远是 1,而当 t 非空而 s 为空的时候,不可能有子序列。综合初始条件和递推关系,就得到了动态规划版的程序:

int numDistinctDP(string S, string T) {
    int dp[T.size() + 1][S.size() + 1];  
    for (int i = 0; i <= S.size(); ++i)
        dp[0][i] = 1;
    for (int i = 1; i <= T.size(); ++i)
        dp[i][0] = 0;
    for (int i = 1; i <= T.size(); ++i)
        for (int j = 1; j <= S.size(); ++j)
            dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1] * (S[j - 1] == T[i - 1]);
    return dp[T.size()][S.size()];  
}

动态规划版少了递归时函数调用的开销,而且程序也更简洁了,运行时间为 4ms,速度提升了四倍,时间复杂度和空间复杂度都为 $O(S T)$。

思路三优化

思路三中空间复杂度还可以进一步优化,可以看出来,递推时我们只用到了 s 的上一个字符时的状态,我们可以压缩空间,只存储关于 t 的状态。这里采用的是类似于 01 背包问题 的一维数组优化技巧。需要注意的是,因为我们需要上一状态的的前一个字符的信息,所以在循环的时候必须倒着循环,否则就破坏了状态。空间优化过的代码如下:

int numDistinct(string S, string T) {
    int dp[T.size() + 1] = {1};
    for (int i = 1; i <= S.size(); ++i)
        for (int j = T.size(); j > 0; --j)
            dp[j] += T[j - 1] == S[i - 1] ? dp[j - 1] : 0;  
    return dp[T.size()];  
}

虽然运行时间没有变化,但是空间复杂度降到了 $O(T)$,程序也更加简洁了。