forked from neetcode-gh/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
0115-distinct-subsequences.java
40 lines (32 loc) · 1.02 KB
/
0115-distinct-subsequences.java
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
// Dynammic Programming - Memoization
// Time Complexity O(s * t) | Space Complexity O(s * t)
class Solution {
public int numDistinct(String s, String t) {
int n = s.length() + 1;
int m = t.length() + 1;
int[][] memo = new int[n][m];
for (int[] row : memo) {
Arrays.fill(row, -1);
}
return recursion(s, t, 0, 0, memo);
}
public int recursion(String s, String t, int sIdx, int tIdx, int[][] memo) {
if (memo[sIdx][tIdx] != -1) {
return memo[sIdx][tIdx];
}
if (tIdx >= t.length()) {
return 1;
}
if (sIdx >= s.length()) {
return 0;
}
if (t.charAt(tIdx) == s.charAt(sIdx)) {
memo[sIdx][tIdx] =
recursion(s, t, sIdx + 1, tIdx + 1, memo) +
recursion(s, t, sIdx + 1, tIdx, memo);
return memo[sIdx][tIdx];
}
memo[sIdx][tIdx] = recursion(s, t, sIdx + 1, tIdx, memo);
return memo[sIdx][tIdx];
}
}