115 Distinct Subsequences

115. Distinct Subsequences

1. Question

Given a string S and a string T, count the number of distinct subsequences of S which equals T.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie,"ACE"is a subsequence of"ABCDE"while"AEC"is not).

Here is an example: S="rabbbit",T="rabbit"

Return3.

2. Implementation

(1) DP

public class Solution {
    public int numDistinct(String s, String t) {
        int m = t.length();
        int n = s.length();

        // dp[i][j] is the number of distinct subsequence in S.substring(0, j) that are equal to T.substring(0, i)
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                // for the first row, empty string(row) is the subsequence of any string
                if (i == 0) {
                    dp[i][j] = 1;
                }
                // for the first column, empty string(column) has no subsequence
                else if (j == 0) {
                    dp[i][j] = 0;
                }
                // if t[i - 1] == s[j - 1], two options:
                // (1) All subsequence without last character in S
                // (1) All subsequence without last character in both
                else if (t.charAt(i - 1) == s.charAt(j - 1)) {
                    dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1];
                }
                // If last characters don't match, the number of distinct subsequences is the same
                // subsequences without the last character in S
                else {
                    dp[i][j] = dp[i][j - 1];
                }
            }
        }
        return dp[m][n];
    }
}

3. Time & Space Complexity

DP: 时间复杂度O(mn), 空间复杂度O(mn)