子序列的数目

题目描述

子序列的数目

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

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

题目数据保证答案符合 32 位带符号整数范围。

思路

二维数组

因为该问题输入为两个字符串，所以状态方程需要两个变量。设 f(i, j) 表示字符串 s 下标从 0 到 i 的子字符串 s[0] ~ s[i] 中等于字符串 t 下标从 0 到 j 的子字符串 t[0] ~ t[j] 的子序列个数。因为若字符串 s 的长度小于字符串 t，那么字符串 s 中肯定不可能存在子字符串使其等于字符串 t，所以当 i < j 时 f(i, j) = 0。当 i >= j 时，若 s[i] != t[j] ，那么无法用 s[i] 去匹配 t[i] 则需要舍去 s[i]，可以得到 f(i, j) = f(i - 1, j)， 表示 s[0] ~ s[i] 中与 t[0] ~ t[j] 相等的子序列个数与s[0] ~ s[i - 1] 中与 t[0] ~ t[j] 相等的子序列个数相同。若 s[i] == t[j]，则既可以舍去 s[i] 不进行匹配也可以使用 s[i] 与 t[j] 进行匹配，可以得到 f(i, j) = f(i - 1, j) + f(i - 1, j - 1)，f(i - 1, j) 表示不进行匹配时的个数，f(i - 1, j - 1) 表示进行匹配的个数，其值代表字符串 s[0] ~ s[i - 1] 中与字符串 t[0] ~ t[j - 1] 相等的子序列个数。故转移方程可以总结为：

上式成立的条件都是 i >= j，另外 f(i, -1) 表示字符串 s[0] ~ s[i] 中与空字符串相等的子序列个数，所以 f(i, -1) = 1，f(i, -1) 表示空字符串中与字符串 t[0] ~ t[j] 相等的子序列个数，所以 j > 0 时 f(-1 ,j) = 0。以 s = “appplep”, t = “apple” 为例子二维 DP 矩阵如下图

若 s 和 t 的长度分别为 m 和 n，那么时间复杂度为 O(mn)，空间复杂度为 O(mn)。

一维数组正序

考虑遍历到如图的标星处

可以发现当前的值只与标红处的值有关，所以可以通过辅助变量把二维数组优化为只需一行的一维数组。完整的代码如下，时间复杂度为 O(mn)，空间复杂度为 O(n)。

一维数组逆序

如果改变从左往右的遍历顺序为从右往左的顺序，如下图，那么可以无需使用辅助变量。

时间复杂度为 O(mn)，空间复杂度为 O(n)。

三种方案的代码实现如下：

代码实现

class Solution {
	public int numDistinct1(String S, String T) {
		char[] s = S.toCharArray();
		char[] t = T.toCharArray();
		// dp[i][j] : s[0..i] T[0...j]

		// dp[i][j] : s只拿前i个字符做子序列，有多少个子序列，字面值等于T的前j个字符的前缀串
		int[][] dp = new int[s.length + 1][t.length + 1];
		// dp[0][0]
		// dp[0][j] = s只拿前0个字符做子序列, T前j个字符
		for (int j = 0; j <= t.length; j++) {
			dp[0][j] = 0;
		}
		for (int i = 0; i <= s.length; i++) {
			dp[i][0] = 1;
		}
		for (int i = 1; i <= s.length; i++) {
			for (int j = 1; j <= t.length; j++) {
				dp[i][j] = dp[i - 1][j] + (s[i - 1] == t[j - 1] ? dp[i - 1][j - 1] : 0);
			}
		}
		return dp[s.length][t.length];

    }

    public int numDistinct2(String S, String T) {
        char[] s = S.toCharArray();
		char[] t = T.toCharArray();
		int[] dp = new int[t.length + 1];
		dp[0] = 1;
		
        for (int i = 1; i <= s.length; i++) {
           int tmp1 = 1;
           int tmp2 = 1;
			for (int j = 1; j <= Math.min(t.length, i); j++) {
	               tmp2 = dp[j];
				dp[j] += s[i - 1] == t[j - 1] ? tmp1 : 0;
	               tmp1 = tmp2;
			}
		}
		return dp[t.length];

    }

    public int numDistinct3(String S, String T) {
        char[] s = S.toCharArray();
		char[] t = T.toCharArray();
		int[] dp = new int[t.length + 1];
		dp[0] = 1;
		
		for (int i = 1; i <= s.length; i++) {
			for (int j = Math.min(t.length, i); j >= 1; j--) {
				dp[j] += s[i - 1] == t[j - 1] ? dp[j - 1] : 0;
			}
		}
		return dp[t.length];

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59