Hi, all. Here is my solution using Dynamic Programming.

Suppose the length of string ** s** is

*m*the length of string

**is**

*t**n*. We can divide this problem into sub-problem of calculating a 2D array

**[**

*A**m*][

*n*+1], where

**[**

*A**i*][

*j*] represents the number of distinct subsequences of

**'s prefix at length**

*s**i*+1 that equals to

**'s prefix at length**

*t**j*.

It's obvious that ** A**[

*i*][

*j*] depends on

**[**

*A**i*-1][

*j*], and

**[**

*A**i*-1][

*j*-1] when

**[**

*t**j*] equals to

**[i]. The reason is the prefix of**

*s***at length**

*s**i*+1 should contain all subsequences of the prefix of

**at length**

*s**i*. Moreover, when

**[**

*t**j*-1] equals to

**[i], we should also plus the number of subsequences of**

*s***'s prefix at length**

*t**j*-1 in the

**'s prefix at length**

*s**i*-1. Thus, the recursion formula is:

[*A**i*][*j*] =[*A**i*-1][*j*] +[*A**i*-1][*j*-1]**if**[*t**j*-1] equals to[i]*s*

Here is an example, ** s** = "abcab",

**= "ab",**

*t***is initialized as follows:**

*A*A |
0 | 1 | 2 |
---|---|---|---|

0 | 1 | 0 | 0 |

1 | 1 | ||

2 | 1 | ||

3 | 1 | ||

4 | 1 |

Let's first calculating ** A**[1][1]. Because

**[0] = 'a' ==**

*t***[0] = 'a',**

*s***[1][1] =**

*A***[0][1] +**

*A***[0][0] = 1. Then, we can calculate**

*A***[1][2], Because**

*A***[1] = 'b' ≠**

*t***[0] = 'a',**

*s***[1][2] =**

*A***[0][2] = 0. We can fill in**

*A***in this way. The final result is shown as follows:**

*A*A |
0 | 1 | 2 |
---|---|---|---|

0 | 1 | 0 | 0 |

1 | 1 | 1 | 0 |

2 | 1 | 1 | 1 |

3 | 1 | 2 | 1 |

4 | 1 | 2 | 3 |

Here, ** A**[4][2] is the result we want. Three subsequences are shown in bold font as follows:

**ab**cab**a**bca**b**- abc
**ab**

Notice that ** A** is calculated in a row-wise manner, we can use an 1D array at length

*n*+1 instead of

**. The code in C++ is shown as follows (3ms, O(m*n) time complexity, O(n) space complexity, 6 lines):**

*A*```
class Solution {
public:
int numDistinct(string s, string t) {
vector<int> match(t.size()+1);
match[0] = 1;
for (int i=0; i<s.size(); i++)
for (int j=t.size(); j>0; j--)
match[j] += (t[j-1] == s[i] ? match[j-1] : 0);
return match[t.size()];
}
};
```

You can also compress the code to 4 lines if you want :)

```
class Solution {
public:
int numDistinct(string s, string t) {
vector<int> match(t.size()+1);
match[0] = 1;
for (int i=0; i<s.size(); i++) for (int j=t.size(); j>0; j--) match[j] += (t[j-1] == s[i] ? match[j-1] : 0);
return match[t.size()];
}
};
```