4ms, 7 lines, c++ dp solution! very clear, almost best!


  • 29
    P

    prefixVec stores the numbers of t's prefixes occur when we iterate through s. the dp equation is when we encounter a character which also occurs in t at position i, then prefixVec[i] += prefixVec[i-1] (i > 0), prefixVec[i]++ (i = 0). we calculate prefixVec backwards so the new value produced won't influence the calculation of next value (at i-1), otherwise we need a temp vector.

    int numDistinct(string s, string t) {
        int tLen = t.size();
        vector<int> prefixVec(tLen,0);
        for (auto c: s)
            for (int i = tLen-1;i >= 0;--i)
                if (t[i] == c)
                    prefixVec[i] = (i > 0 ? prefixVec[i-1] : 1) + prefixVec[i];
        return prefixVec.back();
    }
    
    /*
    example showing how prefixVec is calculated when we eat a new char
    rabbbit rabbit
    
    rabbit 
    000000
    100000 r
    110000 a
    111000 b
    112100 b
    113300 b
    113330 i
    113333 t
    */

  • 0
    H

    Excellent idea!


  • 0
    S

    Brilliant! I have come to similar idea but i stuck into the permutation and combination, such as bbb to bb, thanks for posting your answer!


  • 0
    P

    I use a sentinel, so it's simpler!

    int numDistinct(string s, string t) {
        int tLen = t.size();
        vector<int> prefixVec(tLen+1,0);
        prefixVec[0] = 1;
        for (auto c: s)
            for (int i = tLen-1;i >= 0;--i)
                if (t[i] == c)
                    prefixVec[i+1] += prefixVec[i];
        return prefixVec.back();
    }

  • 0

    cool code and clear idea.


  • 0
    L

    very excellent solution!!!
    but I would like to know how you came out with this solution. When you read this problem, how do you analyze, please kindly help me, because when I met this question, I get totally confused...


Log in to reply
 

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