115. Distinct Subsequences

1. Description

Given two strings s and t, return the number of distinct subsequences of s which equals t.
The test cases are generated so that the answer fits on a 32-bit signed integer.

2. Example

Example 1:
Input: s = “rabbbit”, t = “rabbit”
Output: 3
Explanation:
As shown below, there are 3 ways you can generate “rabbit” from s.
rabbbit
rabbbit
rabbbit

Example 2:
Input: s = “babgbag”, t = “bag”
Output: 5
Explanation:
As shown below, there are 5 ways you can generate “bag” from s.
babgbag
babgbag
babgbag
babgbag
babgbag

3. Constraints

• 1 <= s.length, t.length <= 1000
• s and t consist of English letters.

4. Solutions

Dynamic Programming

m = str.size(), n = sub.size()
Time complexity: O(mn)
Space complexity: O(m)

class Solution {
public:
    int numDistinct(const string &str, const string &sub) {
        vector<vector<unsigned long long>> dp(2, vector<unsigned long long>(str.size() + 1));
        for (int i = 0; i <= str.size(); ++i) {
            dp[0][i] = 1;
        }

        for (int i = 0; i < sub.size(); ++i) {
            dp[1][0] = 0;
            for (int j = 1; j <= str.size(); ++j) {
                if (j < i) {
                    dp[1][j] = 0;
                } else {
                    dp[1][j] = dp[1][j - 1] + (str[j-1] == sub[i] ? dp[0][j - 1] : 0);
                }
            }

            swap(dp[0], dp[1]);
        }

        return dp[0].back();
    }
};