[LeetCode] 115. Distinct Subsequences

Posted on | In

Problem

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).

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
Input: S = "rabbbit", T = "rabbit"
Output: 3
Explanation:

As shown below, there are 3 ways you can generate "rabbit" from S.
(The caret symbol ^ means the chosen letters)

rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^

Example 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Input: S = "babgbag", T = "bag"
Output: 5
Explanation:

As shown below, there are 5 ways you can generate "bag" from S.
(The caret symbol ^ means the chosen letters)

babgbag
^^ ^
babgbag
^^    ^
babgbag
^    ^^
babgbag
  ^  ^^
babgbag
    ^^^

Explanation

  1. We can use dynamic programming to solve this problem.

  2. Dynamic state is a two dimensional array dp[i][j] which represents a S is choosing characters from the beginning to j inclusive (top row), and T is choosing characters from the beginning to i inclusive (left column), the value of dp[i][j] is their result.

  3. Dynamic init is, when both T and S are empty, the result will be 1 because empty S can form empty T. Also actually in the top row all elements are 1 because when T is empty, no matte how many characters we choose from S, they can all form the empty string by choosing the empty string. On the other hand, when S is empty, but T is not empty, then S cannot form T, so left most column values are 0.

  4. Dynamic function can have two cases. First, if the last characters of T and S are the same, then dp[i][j] = dp[i-1][j-1] + dp[i][j-1] because if we don’t choose the last characters from T and S then it’s equal to dp[i-1][j-1], and if we don’t choose the last character from S, then it’s equal to dp[i][j-1]. Second case is when the last character are not the same, so we can only don’t choose the last character from S, so we have dp[i][j] = dp[i][j-1].

  5. Dynamic result is choosing all characters from S and T, which is the bottom right result.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int numDistinct(String s, String t) {
        int sLen = s.length();
        int tLen = t.length();
        int[][] dp = new int[tLen+1][sLen+1];
        for (int col = 0; col < dp[0].length; col++) {
            dp[0][col] = 1;
        }
        for (int row = 1; row < dp.length; row++) {
            for (int col = 1; col < dp[0].length; col++) {
                if (s.charAt(col-1) == t.charAt(row-1)) {
                    dp[row][col] = dp[row-1][col-1] + dp[row][col-1];
                } else {
                    dp[row][col] = dp[row][col-1];
                }
            }
        }

        return dp[tLen][sLen];
    }
}