LC 115 - Distinct Subsequences
Question
Given two strings s and t, return the number of distinct subsequences of s which equals t.
The test cases are generated so that the answer fits on a 32-bit signed integer.
Example 1:
1
2
Input: s = "rabbbit", t = "rabbit"
Output: 3
Explanation: As shown below, there are 3 ways you can generate “rabbit” from s. **rabb**b**it** **ra**b**bbit** **rab**b**bit**
Example 2:
1
2
Input: s = "babgbag", t = "bag"
Output: 5
Explanation: As shown below, there are 5 ways you can generate “bag” from s. **ba**b**g**bag **ba**bgba**g** **b**abgb**ag** ba**b**gb**ag** babg**bag**
Constraints:
1 <= s.length, t.length <= 1000sandtconsist of English letters.
Links
Question here and solution here
Solution
concept
The bottom up solution is very similar to [[1143. Longest Common Subsequence]] where in the 2D grid formed by the 2 words, if the two char matches, we need to take a look at the diagonally right cell. We will have an extra row and column for ease of calculation.
Regardless of char matching or not, the current cell dp[i][j] will take the cell below because we could have skip the char in s. In addition, if the char do match, then we have to add the cell value diagonally right, this is the value if we do use the current char in s (s[i]) to match the char in t (t[j])
s = rabbbit and t = rabbit m = len(s) = 7 and n = len(t) = 6
| t0: r | t1: a | t2: b | t3: b | t4: i | t5: t | t_ | |
|---|---|---|---|---|---|---|---|
| s0: r | 1 | ||||||
| s1: a | 1 | ||||||
| s2: b | 1 | ||||||
| s3: b | 1 | ||||||
| s4: b | 1 | ||||||
| s5: i | 1 | ||||||
| s6: t | X | 1 | |||||
| s_ | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
code
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
class Solution:
def numDistinct(self, s: str, t: str) -> int:
def dfs(i,j):
if j == len(t):
return 1
if i >= len(s):
return 0
if s[i] == t[j]:
ans = dfs(i + 1, j) + dfs(i + 1, j + 1)
else:
ans = dfs(i + 1, j)
return ans
return dfs(0,0)
class Solution:
"""
top down: memoization
"""
def numDistinct(self, s: str, t: str) -> int:
cache = {}
def dfs(i,j):
if (i,j) in cache:
return cache[(i,j)]
if j == len(t):
return 1
if i >= len(s):
return 0
# even if match, we still need to consider skipping to account for future char matching t[j]
if s[i] == t[j]:
ans = dfs(i + 1, j) + dfs(i + 1, j + 1)
else:
ans = dfs(i + 1, j)
cache[(i,j)] = ans
return cache[(i,j)]
return dfs(0,0)
class Solution:
"""
top down: memoization
"""
def numDistinct(self, s: str, t: str) -> int:
cache = {}
def dfs(i,j):
if (i,j) in cache:
return cache[(i,j)]
if j == len(t):
return 1
if i >= len(s):
return 0
ans = dfs(i + 1, j)
if s[i] == t[j]:
ans += dfs(i + 1, j + 1)
cache[(i,j)] = ans
return cache[(i,j)]
return dfs(0,0)
class Solution:
"""
bottom up solution
"""
def numDistinct(self, s: str, t: str) -> int:
dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
for i in range(len(s) + 1):
dp[i][len(t)] = 1
for i in range(len(s) - 1, -1, -1):
for j in range(len(t) - 1, -1, -1):
dp[i][j] = dp[i + 1][j]
if s[i] == t[j]:
dp[i][j] += dp[i + 1][j + 1]
return dp[0][0]
class NeetSolution:
"""
bottom up solution
space optimized
"""
def numDistinct(self, s: str, t: str) -> int:
m, n = len(s), len(t)
dp = [0] * (n + 1)
nextDp = [0] * (n + 1)
dp[n] = nextDp[n] = 1
for i in range(m - 1, -1, -1):
for j in range(n - 1, -1, -1):
nextDp[j] = dp[j]
if s[i] == t[j]:
nextDp[j] += dp[j + 1]
dp = nextDp[:]
return dp[0]
Complexity
time: $O(mn)$
space: $O(mn)$ or $O(n)$