FilesExpand file tree

 main

/

0115-distinct-subsequences.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

40 lines (32 loc) · 1.02 KB

 main

/

0115-distinct-subsequences.java

Copy path

Top

File metadata and controls

• Code
• Blame

40 lines (32 loc) · 1.02 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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];

}

}