115_Distinct_Subsequences.md

115. Distinct Subsequences

---

Description

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

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"

Return 3.

Javascript

/**
 * @param {string} s
 * @param {string} t
 * @return {number}
 */
var numDistinct = function(s, t) {
    if (s.length < t.length) {
        return 0;
    }
    
    if (s.length === t.length) {
        if (s === t) {
            return 1;
        } else {
            return 0;
        }
    }
    
    var ls = s.length;
    var lt = t.length;
    
    var dp = [];
    var i, j;
    for (i = 0; i <= ls; i++) {
        dp.push([]);
        for (j = 0; j <= lt; j++) {
            if (j === 0) {
                dp[i][j] = 1;
            } else {
                dp[i][j] = 0;
            }
        }
    }
    
    for (i = 1; i <= ls; i++) {
        for (j = 1; j <= lt; j++) {
            if (s[i - 1] === t[j - 1]) {
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    
    return dp[ls][lt];
};