Leetcode 115: Distinct Subsequences

https://leetcode.com/problems/distinct-subsequences/description/

Notes:

This question can be solved by dynamic programming.

Let dp[i][j] represents the distinct subsequences in S[0, i] to T[0, j].

When S[i] == T[j], S[i] can be either used to match T[j] or not. Thus,

dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

When S[i] != T[j], S[i] cannot be used to match T[j]. Thus,

dp[i][j] = dp[i-1][j].

See the code below:

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

The space complexity can be further improved to O(N).

[update 12/22/2019]: remove 2 unnecessary lines below. See the commented two lines.

See the code below:

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