LeetCode - Distinct Subsequences
Problem 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).
It’s guaranteed the answer fits on a 32-bit signed integer.
Example 1:
1
2
3
4
5
6
7
8
9
10
11
12
13
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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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
^^^
Analysis
Basically, we can use recursion to analysis this question.
Let’s say we have two pointers at index i of String s and index j of String t. Then if (i != j), then ways(i,j) should equals to the ways(i-1.j). But if char at i == char at j, then there are two possible answers, which is use this char at j or don’t use it. so the ways(i,j) = ways(i+1,j+1) + ways(i+1, j).
So the first solution is recursion with memorization.
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
class Solution {
// Dictionary that we will use for memoization
private HashMap<Pair<Integer, Integer>, Integer> memo;
private int recurse(String s, String t, int i, int j) {
int M = s.length();
int N = t.length();
// Base case
if (i == M || j == N || M - i < N - j) {
return j == t.length() ? 1 : 0;
}
Pair<Integer, Integer> key = new Pair<Integer, Integer>(i, j);
// Check to see if the result for this recursive
// call is already cached
if (this.memo.containsKey(key)) {
return this.memo.get(key);
}
// Always calculate this result since it's
// required for both the cases
int ans = this.recurse(s, t, i + 1, j);
// If the characters match, then we make another
// recursion call and add the result to "ans"
if (s.charAt(i) == t.charAt(j)) {
ans += this.recurse(s, t, i + 1, j + 1);
}
// Cache the result
this.memo.put(key, ans);
return ans;
}
public int numDistinct(String s, String t) {
this.memo = new HashMap<Pair<Integer, Integer>, Integer>();
return this.recurse(s, t, 0, 0);
}
}
Based on this solution, we can have another solution which is DP from bottom to up.
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
class Solution {
public int numDistinct(String s, String t) {
int M = s.length();
int N = t.length();
int[][] dp = new int[M + 1][N + 1];
// Base case initialization
for (int j = 0; j <= N; j++) {
dp[M][j] = 0;
}
// Base case initialization
for (int i = 0; i <= M; i++) {
dp[i][N] = 1;
}
// Iterate over the strings in reverse so as to
// satisfy the way we've modeled our recursive solution
for (int i = M - 1; i >= 0; i--) {
for (int j = N - 1; j >= 0; j--) {
// Remember, we always need this result
dp[i][j] = dp[i + 1][j];
// If the characters match, we add the
// result of the next recursion call (in this
// case, the value of a cell in the dp table
if (s.charAt(i) == t.charAt(j)) {
dp[i][j] += dp[i + 1][j + 1];
}
}
}
return dp[0][0];
}
}
What to improve
- need to improve the skills to find how to use DP.