C++ DP solution with explanation


  • 0
    G
    class Solution {
    public:
    
        //
        // We'll define D[i][j] = the number of distinct subsequences of s[0...i - 1] and t[0...j - 1]
        // D[i][j] = if s[i - 1] == t[j - 1], D[i - 1][j - 1] + D[i - 1][j]
        // else, D[i - 1][j]. 
        //
        int numDistinct(string s, string t) 
        {
            vector<vector<int> > D(s.size() + 1,vector<int>(t.size() + 1,0));
            
            //
            // The empty (T) string is always a substring 
            // of S
            //
            
            for(int i = 0; i < s.size() + 1; ++i)
            {
                D[i][0] = 1;
            }
            
            for(int i = 1; i < s.size() + 1; i++)
            {
                for(int j = 1; j < t.size() + 1; ++j)
                {
                   if(s[i - 1] == t[j - 1])
                   {
                       D[i][j] = D[i - 1][j - 1] + D[i - 1][j];
                   }
                   else
                   {
                       D[i][j] = D[i - 1][j];
                   }
                }
            }
            
            return D[s.size()][t.size()];
        }
    };

Log in to reply
 

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