题目地址:https://leetcode-cn.com/problems/distinct-subsequences/description/
给定一个字符串 S 和一个字符串 T,计算在 S 的子序列中 T 出现的个数。
一个字符串的一个子序列是指,通过删除一些(也可以不删除)字符且不干扰剩余字符相对位置所组成的新字符串。(例如,"ACE"
是 "ABCDE"
的一个子序列,而 "AEC"
不是)
比如:S = "rabbbit", T = "rabbit"
,则输出 3
。
思路一
最简单直接的思路就是暴力枚举 S
的所有子序列,然后逐一比较,时间复杂度为 $O(2^n)$,显然是不可接受的。
思路二
一个比较容易想到的思路是递归求解,先在 S
中找到 T
的第一个字符,然后每找到一个就从 S
的下一个位置开始递归找 T
的下一个字符,递归的边界条件就是 T
的下标为 T
的长度,这时候说明找到了一个子序列,返回 1
,然后将结果累加即可。代码如下:
函数中 s_i
和 t_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)$,程序也更加简洁了。