749e0b3f460fc18da71550d62cf08ebd
(难度Hard) Problem 115. Distinct Subsequences(所有子序列种数)

Distinct Subsequences

Difficulty

Hard

Description

Given a string S and a string T , count the number of distinct
subsequences of S which equals T.

A subsequence of a string is a new string which is formed from the original
string by deleting some (can be none) of the characters without disturbing the
relative positions of the remaining characters. (ie, "ACE" is a subsequence
of "ABCDE" while "AEC" is not).

Example 1:

Input: S = "rabbbit", T = "rabbit"
Output:  3
## Explanation:
As shown below, there are 3 ways you can generate  "rabbit" from S.
(The caret symbol ^ means the chosen letters)

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

Example 2:

Input: S = "babgbag", T = "bag"
Output:  5
## Explanation:
As shown below, there are 5 ways you can generate  "bag" from S.
(The caret symbol ^ means the chosen letters)

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

题意

给定两个字符串s和t,求有多少种不同的办法,从s中去掉部分字符使它和t相等。

题解

我们拿到题目正向思考是比较难的,因为我们想不到一个很好的方法可以计算s变成t的方法数。即使我们简化难度把s变成s的子串,对我们来说也没有差别, 因为两者用的方法应该是一样的。母串我们不知道怎么办,子串同样束手无策。

所以我们需要换一个方法,不妨逆向思考一下。假设我们当下是两个空串,我们需要往里面添加元素。但是在添加的时候,有一个规则,就是t当中的元素只有和s中元素对应上的时候才能往里添加。我们想要求解把t添加完的方法数,怎么办?

很简单,我们用状态转移。

我们用s[i], t[j]表示当下用到的s串和t串的位置。意味着s串i位置之前,t串j位置之前的元素都已经被使用了,那么接下来应该怎么办呢?很简单,我们判断s[i] 和 t[j],如果s[i] == t[j], 那么我们可以考虑把j加进来,当然也可以不加。所以从s[i], t[j]的状态我们可以推导到s[i+1], t[j+1] 以及 s[i+1], t[j]。所以,i, j就是状态,我们用一个pair就可以存储。

状态有了,我们只需要在t数组放完的时候把答案+1,就可以得到最终的结果。

我们需要用队列存储所有当下可以达到的状态,在本问题当中,状态之间是有顺序的,i,j都往增大的趋势发展,所以不用担心会无限循环。

top Created with Sketch.