[How to from Error to AC to Better]thoughts and extensions with C++ implementation


  • 0

    At my first analysis I think about to use the

     dp[i][j] : refers the count of the  T[0..j-1]  happens in the S[0...i-1]
    

    So the condition is like this

        if s[i-1]==t[j-1]       dp[i][j] = dp[i-1][j-1]
    
        else         dp[i][j] = dp[i-1][j]
    

    But of course this is wrong as the count never add new number.

    So where happens wrong ?

    Using the tail DP idea, I know it is that we use the bool DP equation but not the count DP equation.

    When s[i-1]==t[j-1] , we can also use dp[i-1][j] to count the case we not use the tail element.

    So the right equation should be like this:

        if s[i-1]==t[j-1]       dp[i][j] = dp[i-1][j-1]+dp[i-1][j]
    
        else         dp[i][j] = dp[i-1][j]
    

    AC code implementation

      class Solution {
        public:
            int numDistinct(string s, string t) {
                int ss=s.size(), tt=t.size();
                /** dp[i][j] means t[0..j-1] appears in s[0...i-1] for ** times. 
                 *  if s[i-1]==t[j-1]   
                 *     dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
                 *  else
                 *     dp[i][j] = dp[i-1][j]
                 **/
                 vector<vector<int>> dp(ss+1, vector<int>(tt+1, 0));
                 for(int i=0; i<=ss; i++){
                     for(int j=0; j<=tt; j++){
                         if(i==0 && j==0) dp[i][j]=1;
                         else if(i==0)  dp[i][j]=0;
                         else if(j==0)  dp[i][j]=1;
                         else dp[i][j]=dp[i-1][j]+(s[i-1]==t[j-1] ? dp[i-1][j-1]:0);
                     }
                 }
                 return dp[ss][tt];
            }
        };
    

    Here is the compressed DP version using rolling array.

    class Solution {
    public:
        int numDistinct(string s, string t) {
            int ss=s.size(), tt=t.size();
            /** dp[i][j] means t[0..j-1] appears in s[0...i-1] for ** times. 
             *  if s[i-1]==t[j-1]   
             *     dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
             *  else
             *     dp[i][j] = dp[i-1][j]
             **/
             vector<vector<int>> dp(2, vector<int>(tt+1, 0));
             for(int i=0; i<=ss; i++){
                 for(int j=0; j<=tt; j++){
                     if(i==0 && j==0) dp[i&1][j]=1;
                     else if(i==0)  dp[i&1][j]=0;
                     else if(j==0)  dp[i&1][j]=1;
                     else dp[i&1][j]=dp[(i-1)&1][j]+(s[i-1]==t[j-1] ? dp[(i-1)&1][j-1]:0);
                 }
             }
             return dp[ss&1][tt];
        }
    };

  • 0
    2

    When I first implement this, I made an error at that I create the array of wrong size ...........

    I should create size of (size_s+1) * (size_t+1)

    Because the dp[0][I] : means nothing match one char ...

    So the DP array dimention should be one bigger than the original data array ...

    class Solution {
    public:
        int numDistinct(string s, string t) {
            int size_s = s.size(), size_t = t.size();
            vector<vector<int>> dp(size_s + 1, vector<int>(size_t + 1, 0));
            for(int i = 0; i <= size_s; i++){
                for(int j = 0; j <= size_t; j++) {
                    if(j == 0)  { dp[i][j] = 1; continue; }
                    if(i == 0)  continue;
                    dp[i][j] += dp[i-1][j];
                    if(s[i-1] == t[j-1])  dp[i][j] += dp[i-1][j-1];
                }
            }
            return dp[size_s][size_t];
        }
    };

  • 0
    F
    class Solution {
    public:
        int numDistinct(string s, string t) {
            if(s.size() < t.size() || s.empty() && !t.empty())
                return 0;
            if(t.empty())
                return 1;
                
            vector<vector<int>> f(s.size()+1,vector<int>(t.size()+1,0));
            f[0][0] = 1;
            
            for(int i = 0; i <= s.size(); i++)
                f[i][0] = 1;
             
            for(int i = 1; i <= s.size(); i++){
                for(int j = 1; j <= t.size(); j++){
                    if(j > i) break;
                    if(s[i-1] != t[j-1])
                        f[i][j] = f[i-1][j];
                    else
                        f[i][j] = f[i-1][j-1] + f[i-1][j];
                }
            }
            
            return f[s.size()][t.size()];
        }
    };
    

    at first I wrote if(s[i-1] != s[j-1]) and I was confused because it actually passed many tests and seemed like a legit program that had some corner cases, but it was actually just a typo


Log in to reply
 

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