不同的子序列统计

发表于

算法：动态规划



题目

url：https://leetcode-cn.com/problems/distinct-subsequences/

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

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

示例 1：

1
2
3
4
5
6
7
8
9
10
11
12
13
输入: S = "rabbbit", T = "rabbit"
输出: 3
解释:

如下图所示, 有 3 种可以从 S 中得到 "rabbit" 的方案。
(上箭头符号 ^ 表示选取的字母)

rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^

示例 2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
输入: S = "babgbag", T = "bag"
输出: 5
解释:

如下图所示, 有 5 种可以从 S 中得到 "bag" 的方案。 
(上箭头符号 ^ 表示选取的字母)

babgbag
^^ ^
babgbag
^^    ^
babgbag
^    ^^
babgbag
  ^  ^^
babgbag
    ^^^


分析

动态规划的本质是穷举法

拿第二个示例分析，S = “babgbag”, T = “bag”

b 在S中出现的可能性，存；b后a出现的可能性，存储；在ba的基础上g出现的可能性储存；

Snipaste_2019-07-31_14-26-10.jpg

二维数组的解法，转化为1位数组的解法



Java解法

s的长度为n，t的长度为m，空间复杂度为O(m)的解法如下：

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
class Solution {
	public int numDistinct(String s, String t) {
		int sl = s.length();
		int tl = t.length();
		if(sl==0||tl==0)return 0;
		if(sl<tl)return 0;
		if(sl==tl)return s.equals(t)?1:0;
		int[] res = new int[tl+1];
		for(int i=0;i<sl; i++){
			int pre=0;
			for(int j=0;j<tl; j++){
				if(j==0)pre=1;
				int temp = res[j+1];
				if(s.charAt(i)==t.charAt(j)){
					res[j+1]=res[j+1]+pre;
				}
				pre = temp;
			}
		}
		return res[tl];
	}
}
public class App {
	public static void main(String[] args) throws IOException {
		int num = new Solution().numDistinct("babgbag", "bag");
		System.out.println(num);
	}
}

pre和temp的作用是 记录本轮更改之前的值，用于计算，防止”rabbbit”, “rabbit”这样的数据，一个s中的b，影响多个t中的b的计算