# 7-10 lines C++ Solutions with Detailed Explanations (O(m*n) time and O(m) space)

• Well, a dynamic programming problem. Let's first define its state `dp[i][j]` to be the number of distinct subsequences of `t[0..i - 1]` in `s[0..j - 1]`. Then we have the following state equations:

1. General case 1: `dp[i][j] = dp[i][j - 1]` if `t[i - 1] != s[j - 1]`;
2. General case 2: `dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1]` if `t[i - 1] == s[j - 1]`;
3. Boundary case 1: `dp[0][j] = 1` for all `j`;
4. Boundary case 2: `dp[i][0] = 0` for all positive `i`.

Now let's give brief explanations to the four equations above.

1. If `t[i - 1] != s[j - 1]`, the distinct subsequences will not include `s[j - 1]` and thus all the number of distinct subsequences will simply be those in `s[0..j - 2]`, which corresponds to `dp[i][j - 1]`;
2. If `t[i - 1] == s[j - 1]`, the number of distinct subsequences include two parts: those with `s[j - 1]` and those without;
3. An empty string will have exactly one subsequence in any string :-)
4. Non-empty string will have no subsequences in an empty string.

Putting these together, we will have the following simple codes (just like translation :-)):

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

Notice that we keep the whole `m*n` matrix simply for `dp[i - 1][j - 1]`. So we can simply store that value in a single variable and further optimize the space complexity. The final code is as follows.

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

• Thanks so much for your detailed explanation on the boundary case. that's an important point in solving this problem.

• I can not understand the optimization, could you please explain as detailed as possible？

• Actually your code can be further improved on space by traversing index i backward. This way you dont need an extra variable to keep the last dp value. Here is my code:

``````int numDistinct(string s, string t) {
int n = s.length(), m = t.length();
vector<int> dp(m+1, 0);
dp[0] = 1;
for (int j = 1; j <= n; j++){
for (int i = m; i >= 1; i--){
dp[i] += s[j-1] == t[i-1] ? dp[i-1] : 0;
}
}
return dp[m];
}
``````

• If t[i - 1] == s[j - 1], the number of distinct subsequences include two parts: those with s[j - 1] and those without;

I think in this sentence you may should mean "If t[i - 1] == s[j - 1], the number of distinct subsequences include two parts: those with t[i - 1] and those without;"

• Javascript version:

``````var numDistinct = function(s, t) {
var m = t.length, n = s.length;
var cur = new Array(m+1);
cur.fill(0)
cur[0] = 1;
for(var j = 1; j <= n; j++) {
var pre = 1;
for(var i = 1; i <= m; i++) {
var temp = cur[i];
cur[i] = cur[i] + (t[i-1] == s[j-1] ? pre : 0);
pre = temp;
}
}
return cur[m];
};
``````

Golang version:

``````func numDistinct(s string, t string) int {
m := len(t)
n := len(s)
cur := make([]int, m+1)
for k,_ := range cur {
cur[k] = 0
}
cur[0] = 1
for j := 1; j <= n; j++ {
pre := 1
for i := 1; i <= m; i++ {
temp := cur[i]
a := 0
if t[i-1] == s[j-1] {
a = pre
}
cur[i] = cur[i] + a
pre = temp;
}
}
return cur[m]
}
``````

• @tonygogogo Mind blown, can you explain the logic that allowed you to come up with the answer?

• @jianchao.li.fighter I do not agree with your boundary cases:

• 1st, `dp[0][j]` represent number of distinct sequences from an empty string `s` equals any string with length `j`, then `dp[0][j] = 0` for all `j`
• 2nd, `dp[i][0]` represent number of distinct sequences from any string with length `i` equals an empty string `t = ""`, and such distinct sequence exists and only can be an empty string `""`, so `dp[i][0] = 1`

right ?

• ``````class Solution {
public:
int numDistinct(string s, string t) {
//dp
int m = s.size();
int n = t.size();
vector<vector<int>> dp(m+1,vector<int>(n+1,0));
int sum = 0;
dp[0][0] = 1;

for(int i=1;i<m+1;i++)
{
for(int j=1;j<n+1;j++)
{
if(s[i-1]==t[j-1])
{
int k = 0;
while (k < i)
{
dp[i][j] += dp[k++][j - 1];
}
}

}
sum += dp[i][n];
}
return sum;

}
};
``````

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