My c++ DP solution with O(m*n) time as well as space complexity

• When constructing the dp table, dp[j][i] means we take the first j characters in S and the first i characters in T into consideration. Then the logic is:

1. the jth of S and ith of T are the same: dp[j][i] should equal to dp[j-1][i-1]+dp[j-1][i]. Where dp[j-1][i-1] means the number of combinations that if we force the ith of T to locate on the jth of S. And dp[j-1][i] means the number of combinations that if we force the ith of T NOT to locate on the jth of S.

2. the jth of S and ith of T are different: dp[j][i] should equal to only dp[j-1][i], which is the number of combinations that we force the ith of T NOT to locate on the jth of S.

And the code also deals with the initial values of the dp table.

``````    class Solution {
public:

int numDistinct(string S, string T) {
vector<vector<int>> dp(S.length() + 1, vector<int>(T.length() + 1, 0));
for (int i = 0; i <= S.length(); ++i) dp[i][0] = 1;

for (int i = 1; i <= T.length(); ++i) { // i is for T
for (int j = i; j <= S.length(); ++j) { // j is for S
if (S[j - 1] == T[i - 1]) {
dp[j][i] = dp[j - 1][i - 1] + dp[j - 1][i];
}
else {
dp[j][i] = dp[j-1][i];
}
}
}

return dp[S.length()][T.length()];
}
};``````

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