16 line C++ solution with O(mn) time and O(m) space


  • 0
    C

    The basic idea is to go through the S string from start. For any s[i], find if there is a match in T string. If it hits, add DP[j-1] to DP[j],
    where DP[j] stands for numbers of subsequences ending with with t[j].
    For example,
    S:"abcbc"
    T:"abc"
    When s[i] == 'c', then add up the number of all the distinct subsequences ending with 'b'(that is DP[2] +=DP[1]).
    That is when i == 2, there is only one subsequences ending with b, DP[2] = 0+DP[1] = 1.
    when i ==4, there are two subsequences ending with b, DP[2] = 1+ DP[1] = 3.

    Note that we count j from up to bottom, so when there is duplicates in T, it still works.

    class Solution {
    public:
        int numDistinct(string s, string t) {
            vector<int> DP(t.size());
            for(int i=0;i<s.size();i++)
                for(int j =t.size()-1;j>=0;j--)
                    if(s[i] == t[j]){
                        if(j == 0)
                            DP[0]++;
                        else
                            DP[j]+=DP[j-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.