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

• 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
*/``````

• Excellent idea！

• 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!

• 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();
}``````

• cool code and clear idea.

• 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...

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