Distinct Subsequences

leetcode 115.

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.

Solution is from here. This one is a dp problem. It is a bit hard to think about.

Let’s say f(S, T) is the number of distinct subsequence between S and T. We have S = S1 S2 S3 S4 S5 S6, T = T1 T2 T3.

First, we know that f(S1 S2 S3 S4 S5 S6, T1 T2 T3) contains f(S1 S2 S3 S4 S5, T1 T2 T3).

Second, we know that if S6 == T3, f(S1 S2 S3 S4 S5 S6, T1 T2 T3) contains f(S1 S2 S3 S4, T1 T2).

In this way, we have the formula to calculate f(S1 S2 S3 S4 S5 S6, T1 T2 T3):

Besides, below is a dp[][] for acdabefbc and abc. Hope this will be helpful to understand. The first line means that an empty string T only has 1 match with string S.

Check my code on github.

public static int numDistinct(String S, String T) {
    int rowNum = T.length() + 1, colNum = S.length() + 1;
    int[][] dp = new int[rowNum][colNum];
    for (int i = 0; i < colNum; i++) {
        dp[0][i] = 1;
    }
    for (int row = 1; row < rowNum; row++) {
        for (int col = 1; col < colNum; col++) {
            dp[row][col] = dp[row][col - 1] + (S.charAt(col - 1) == T.charAt(row - 1) ? dp[row - 1][col - 1] : 0);
        }
    }
    return dp[rowNum - 1][colNum - 1];
}