Easy C++ DP solution, O(N) space, O(MN) time


  • 0

    Let dp(i,j) := distinct sub-sequences of s(i) and t(j), s(i) is substring s[0]...s[i].

    Let's separate the case according to whether s[i] == t[j].

    1. If s[i] == t[j], consider s(i-1) s[i] and t(j-1) t[j].
      1. There are dp(i-1, j-1) subsequence pairs ending with exactly s[i] and t[j].
      2. There are dp(i-1, j) subsequence pairs ending with a letter in s(i-1) and t[j].
      3. So, dp(i,j) = dp(i-1, j-1) + dp(i-1, j)
    2. If s[i] != t[j], you have to use t(j) to looks for sub-sequences in s(i-1), So, dp(i,j) = dp(i-1, j).

    NOTE: in the above analysis, for simplicity, I denote dp(i,j) := distinct sub-sequences of s(i) and t(j). In the real code, considering the initial values (e.g. dp(i, 0) and dp(0, j), Actually dp(i, j) := DS of s(i-1) and t(j-1).

    Corner case:

    1. When matching s with "", regard there is one DS, i.e. dp(i, 0) = 1 (Specially dp(0, 0) = 1)
    2. When matching "" with t, regard there is no DS, i.e. dp(0, j) = 0
    class Solution {
    public:
        int numDistinct(string s, string t) {
            int M = s.size(), N = t.size();
            vector<vector<int>> dp(M + 1, vector<int>(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];
        }
    };
    

    Since dp(i,j) only depends on dp(i-1, j-1) and dp(i-1, j), it's easy to reduce the 2D array into 1D.

    class Solution {
    public:
        int numDistinct(string s, string t) {
            int M = s.size(), N = t.size();
            vector<int> 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];
                    }
                }
            }
            return dp[N];
        }
    };
    

Log in to reply
 

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