Distinct Subsequences LeetCode solution in Java

1
class Solution {
2
  // We assume that dp[i][j] gives us the total number of distinct subsequences for the string s[0
3
  // to i] which equals string t[0 to j]
4
  int f(int i, int j, String s, String t, int dp[][]) {
5
    // If t gets exhausted then all the characters in t have been matched with s so we can return 1
6
    // (we found a subsequence)
7
    if (j < 0) return 1;
8
    // if s gets exhausted then there are characters remaining in t which are yet to be matched as s
9
    // got exhausted they could not be matched so there is no distinct subsequence
10
    if (i < 0) {
11
      return 0;
12
    }
13
    if (dp[i][j] != -1) return dp[i][j];
14
    // If both the characters in s[i] and t[j] match then we have two case
15
    // 1) Either consider the i'th character of s and find the remaining distinct subsequences of
16
    // s[0 to i-1] which equals t[0 to j-1] set i.e. f(i-1,j-1)
17
    // 2) Do not consider s[i] so we are still at the same j'th character of t as we had not been
18
    // considering s[i] matched with t[j] we check distinct subsequences of t[0 to j] in s[0 to i-1]
19
    // i.e. f(i-1,j)
20
    if (s.charAt(i) == t.charAt(j)) {
21
      dp[i][j] = f(i - 1, j - 1, s, t, dp) + f(i - 1, j, s, t, dp);
22
    }
23
    // If both of them do not match then we consider the 2nd case of matching characters
24
    else {
25
      dp[i][j] = f(i - 1, j, s, t, dp);
26
    }
27
    return dp[i][j];
28
  }
29

30
  public int numDistinct(String s, String t) {
31
    int n = s.length();
32
    int m = t.length();
33
    int dp[][] = new int[n][m];
34
    for (int i = 0; i < n; i++) {
35
      Arrays.fill(dp[i], -1);
36
    }
37
    return f(n - 1, m - 1, s, t, dp);
38
  }
39
}