Description

LeetCode 115

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:

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:

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 ^^^

Analysis

It is easy to come up with dynamic programming for a problem with two strings. However, the substructure is skillful to find.

First consider about the corner conditions. If the length of \(s\) is \(0\) and the length of \(t\) is not \(0\), it is impossible to find a valid subsequence. If the length of \(t\) is \(0\), there must be a valid subsequence.

Then consider about the general conditions. If the last character of \(s\) and \(t\) is different, then we should remove the last character of \(s\) and recur for remaining strings. Otherwise, we should sum two counts. The first count is from comparing based on the fact that the two character has been matched. It is the result from removing the last character of \(s\) and the last character of \(t\). The other count is from considering about other characters in \(s\) can also match with the last character of \(t\). It is the result from removing the last character of \(s\).

The process above can easily be described as dynamic programming. The time and space are both \(O(m*n)\), where \(m\) is the size of \(s\) and \(n\) is the size of \(t\).

Solution

class Solution {
    public int numDistinct(String s, String t) {
        int[][] dp=new int[s.length()+1][t.length()+1];
        for(int i=0;i<=s.length();i++) dp[i][0]=1;
        for(int j=1;j<=t.length();j++) dp[0][j]=0;
        for(int i=1;i<=s.length();i++)
        {
            for(int j=1;j<=t.length();j++)
            {
                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[s.length()][t.length()];
    }
}

Reference

[1] https://www.geeksforgeeks.org/count-distinct-occurrences-as-a-subsequence/

Leave a Reply

Your email address will not be published. Required fields are marked *