Question

link

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.

Stats

Frequency 2
Difficulty 4
Adjusted Difficulty 5
Time to use --------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is an extremely difficult DP question, probably the most difficult DP on leetcode.

Normally, string matching question is best solved with DP, so is this question. The problem is how to construct the Bellman equation (also known as dynamic programming equation).

Updated on June 24th, I listed down one example using S = “abab” and T = “ab”.

{} a b
{} 1 0 0
a 1 1 0
b 1 1 1
a 1 2 1
b 1 2 3

Solution

It took me a really long time to understand, until I read this blog.

Let W(i, j) stand for the number of subsequences of S(0, i) in T(0, j). If S.charAt(i) == T.charAt(j), W(i, j) = W(i-1, j-1) + W(i-1,j); Otherwise, W(i, j) = W(i-1,j).

Two code are posted below, realizing this solution with 2D and 1D array respectively (first code is better).

Code

First, DP code

public int numDistinct(String S, String T) {
    int m = S.length(), n = T.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 0; i <= m; i ++) {
        for (int j = 0; j <= n; j ++) {
            if (j == 0) dp[i][j] = 1;
            else if (i == 0) dp[i][j] = 0;
            else 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];
}

Second, same solution but reduced 2-D array to 1-D.

Code readability is reduced, however.

public int numDistinct(String S, String T) {
    int m = S.length(), n = T.length();
    int[] dp = new int[n + 1];
    for (int i = 0; i <= m; i ++) {
        for (int j = n; j >= 0; j --) {
            if (j == 0)
                dp[j] = 1;
            else if (i == 0)
                dp[j] = 0;
            else if (S.charAt(i-1) == T.charAt(j-1))
                dp[j] = dp[j-1] + dp[j];
        }
    }
    return dp[n];
}