Distinct Subsequences

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:

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:

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 <= 1000
• s and t consist of English letters.

Approach - Tabulation 2D

• similar

class Solution {
    public int numDistinct(String s, String t) {
        int m = s.length(), n = t.length();
        int[][] dp = new int[m+1][n+1];
 
        for (int i = 0; i <= m; i++)
            dp[i][n] = 1;
 
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (s.charAt(i) == t.charAt(j))
                    dp[i][j] = dp[i+1][j+1] + dp[i+1][j];
                else
                    dp[i][j] = dp[i+1][j];
            }
        }
 
        return dp[0][0];
    }
} 

Approach - Memoization

• Similar
• O(m*n), O(m*n)

class Solution {
    private Integer[][] dp;
 
    public int numDistinct(String s, String t) {
        int m = s.length(), n = t.length();
        dp = new Integer[m][n];
        return dfs(s,t,0,0);
    }
 
    public int dfs(String s, String t, int i, int j) {
        if (j == t.length()) return 1;
        if (i == s.length()) return 0;
 
        if (dp[i][j] != null)
            return dp[i][j];
 
        if (s.charAt(i) == t.charAt(j))
            return dp[i][j] = dfs(s,t,i+1,j+1) + dfs(s,t,i+1,j);
        else
            return dp[i][j] = dfs(s,t,i+1,j);
    }
}

Approach - Recursion

• if T is exhausted then we count 1 and if s is exhausted then we end the count
• If character matches then we can either move both forward or we can just move the first one and else we just move the first one forward
• O(2^(m+n)), O(m+n)

class Solution {
    public int numDistinct(String s, String t) {
        return dfs(s,t,0,0);
    }
 
    public int dfs(String s, String t, int i, int j) {
        if (j == t.length()) return 1;
        if (i == s.length()) return 0;
 
        if (s.charAt(i) == t.charAt(j))
            return dfs(s,t,i+1,j+1) + dfs(s,t,i+1,j);
        else
            return dfs(s,t,i+1,j);
    }
}