# 3ms, 4-6 lines DP solution in C++, O(m*n) time complexity, O(n) space complexity

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

Suppose the length of string s is m the length of string t is 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's prefix at length i+1 that equals to t's prefix at length 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 s[i]. The reason is the prefix of s at length i+1 should contain all subsequences of the prefix of s at length i. Moreover, when t[j-1] equals to s[i], we should also plus the number of subsequences of t's prefix at length j-1 in the s's prefix at length 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 s[i]

Here is an example, s = "abcab", t = "ab", A is initialized as follows:

A 0 1 2
0 1 0 0
1 1
2 1
3 1
4 1

Let's first calculating A[1][1]. Because t[0] = 'a' == s[0] = 'a', A[1][1] = A[0][1] + A[0][0] = 1. Then, we can calculate A[1][2], Because t[1] = 'b' ≠ s[0] = 'a', A[1][2] = A[0][2] = 0. We can fill in A in this way. The final result is shown as follows:

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:

• abcab
• abcab
• abcab

Notice that A is calculated in a row-wise manner, we can use an 1D array at length n+1 instead of A. The code in C++ is shown as follows (3ms, O(m*n) time complexity, O(n) space complexity, 6 lines):

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

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