115. Distinct Subsequences

/**
 * Using Dynamic Programming (2D Array). See second solution using 1D array.
 *
 * Create a 2D DP array of rows = s.length()+1 and cols = t.length()+1.
 * DP[i+1][j+1] = Number of distinct subsequences of S[0..i] which equals to
 * T[0..j].
 *
 * First Column DP[i][0] = 1. That's because the empty string is a subsequence
 * of any string but only 1 time.
 *
 * First Row DP[0][j] = 0 (except DP[0][0] = 1). This is because an empty string
 * cannot contain a non-empty string as a substring.
 *
 * From here we can easily fill the whole grid:
 *
 * If S[i] != T[j] => Number of distinct subsequences will remain same as the
 * number of subsequences without S[i] character. DP[i][j] = DP[i-1][j].
 *
 * If S[i] == T[j] => Number of distinct subsequences will be the summation of
 * number of subsequences without S[i] & T[j] character and number of
 * subsequences without S[i] character. DP[i][j] = DP[i-1][j-1] + DP[i-1][j].
 *
 * Time Complexity: O(M * N)
 *
 * Space Complexity: O(M * N)
 *
 * M = Length of the string S. N = Length of the string T.
 */
class Solution {
    public int numDistinct(String s, String t) {
        if (s == null || t == null || s.length() < t.length()) {
            return 0;
        }
        int m = s.length();
        int n = t.length();
        if (n == 0) {
            return 1;
        }

        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return dp[m][n];
    }
}

/**
 * Using Dynamic Programming (1D Array - Space Optimized).
 *
 * Logic Explaination see above solution's comments.
 *
 * Time Complexity: O(M * N)
 *
 * Space Complexity: O(N)
 *
 * M = Length of the string S. N = Length of the string T.
 */
class Solution {
    public int numDistinct(String s, String t) {
        if (s == null || t == null || s.length() < t.length()) {
            return 0;
        }
        int m = s.length();
        int n = t.length();
        if (n == 0) {
            return 1;
        }

        int[] dp = new int[n + 1];
        dp[0] = 1;

        for (int i = 1; i <= m; i++) {
            for (int j = n; j >= 1; j--) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[j] += dp[j - 1];
                }
            }
        }

        return dp[n];
    }
}