C++ DP 3ms 3 lines short solution


  • 0
    B

    115 Distinct Subsequences C++ DP

    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.

    Solution

    DP

    Let dp[n] represent the count of prefix T[0..n] seen so far in S
    Initial: dp[*] = 0

    Recurrance:
    dp[n] depends on dp[n-1] and dp[n]

    To illustrate consider this example:
    S="RRABAB", T="RAB"
    initially: dp = [0, 0, 0] #[R A B]
    Lets iterate over S

    s='R'  => dp = [1 0 0]
    s='R'  => dp = [2 0 0]   # We have already seen the prefix 'R' so add one more
    s='A'  => dp = [2 2 0]   # We have seen 2 R's and we see one A so 2 RA's are possible
    s='B'  => dp = [2 2 2]   # 2 RA's seen earlier + B => 2 RAB's
    s='A'  => dp = [2 4 2]   # 2 RA's seen earlier + 2 R's before this A => 4RAs
    s='B'  => dp = [2 4 6]   # 2 RAB's seen earlier + 4 RA's before this B => 6RABs
    

    This can be summarised in this relationship for each iteration:
    dp[n] = dp[n] + dp[n-1]

    With repeating characters in T the key is to apply the relationship from the farthest character towards the earlier character.

    S="RRAABAB"
    T="RAAB"
    
    -  [0 0 0 0]
    R  [1 0 0 0]
    R  [2 0 0 0]
    A  [2 2 0 0]  # 'A' at 2 followed by 'A' at 1
    A  [2 4 2 0]  # 'A' at 2 followed by 'A' at 1 
    B  [2 4 2 2]
    A  [2 6 6 2]  # 'A' at 2 followed by 'A' at 1
    B  [2 6 6 8]
    

    C++ Code

        int numDistinct(string s, string t) {
            vector<int> dp(t.size(), 0);
            for(auto c: s)
                for(auto pos = t.size(); pos and (pos = t.find_last_of(c, pos-1))!=string::npos;)
                    dp[pos] += pos?dp[pos-1]:1;
            return dp[t.size()-1];
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.