115 Distinct Subsequences

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"

Return 3.

Analysis

link:

https://www.youtube.com/watch?v=JI0CuDwh5qI

https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/DistinctSubsequence.java

Solution from Git

public int numDistinct(String s, String t) {
    if (s.length() == 0 || t.length() == 0) {
        return 0;
    }
    int[][] T = new int[s.length() + 1][t.length() + 1];
    for (int i = 0; i < T.length; i++) {
        T[i][0] = 1;
    }
    for (int i = 1; i < T.length; i++) {
        for (int j = 1; j < T[0].length; j++) {
            if (s.charAt(i - 1) == t.charAt(j - 1)) {
                T[i][j] = T[i-1][j-1] + T[i - 1][j];
            } else {
                T[i][j] = T[i - 1][j];
            }
        }
    }
    return T[s.length()][t.length()];
}