LeetCode 115. Distinct Subsequences [Hard] [C++] 解題筆記

 這題給定兩個字串 S 和 T，要我們求 S 有多少個相異子序列等於 T。

EX:

    Input: S = "rabbbit", T = "rabbit"

    Output: 3

    Explanation:
    As shown below, there are 3 ways you can generate "rabbit" from S.
    (The caret symbol ^ means the chosen letters)

  rabbbit
    ^^^^ ^^
  rabbbit
    ^^ ^^^^
  rabbbit
    ^^^ ^^^

想法:

    通常遇到子串,子序列之類的題目多半就是使用 DP 來求解拉，這題也一樣，我們可以用 dp[i][j] 表示 s[0:i-1]

的子序列中等於 t[0:j-1] 的相異子序列個數。則可得到 dp 轉移方程如下:

         dp[i][j] = dp[i - 1][j], if s[i - 1] != t[j - 1]

         dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1], if s[i - 1] == t[j - 1]

這邊可以這樣想，如果說 s 的第 i 個字元不等於 t 的第 j 個字元則表示 t[0:j - 1] 只能從 s[0: i - 2] 的子序列

形成，因此 dp[i][j] 的個數會等於 dp[i - 1][j] (因為 s 多了一個字元並沒有起到作用所以有跟沒有一樣)，而若 s[i - 1] == t[j - 1]

表示要形成 t[0:j - 1] 可以從 s[0: i - 2] 直接形成，也可以從 s[0:i - 2] 形成 t[0:j - 2] 然後在加上與 t[j - 1]相等的s[i - 1]

來形成 t[0:j-1]，因此 dp[i][j] 為兩種方式的方法數相加 => dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]。

另外需要注意的是初始化條件，因為當 t 為空字串時 s 不論是啥都可以形成 t，因此 dp[i][0] = 1, for all i >= 0。

最後，透過觀察我們可以發現到在整個 dp 陣列建構的過程中，我們只需要有前一列(i-1)與前一列前一行(i-1,j-1)的資訊就可以了，

因此可以做空間上的優化並不需要用到一個 s.size() x t.size() 的二維陣列，只需要宣告一個一維陣列和一個變數紀錄 dp[i - 1][j - 1] 的

值即可。

Complexity: O(mxn) time, O(mxn)/O(m) space, where m is size of s, n is size of t。

完整程式碼:

解法一(O(mxn) space DP):

class Solution {
public:
    int numDistinct(string s, string t) {
        // dp[i][j] means the number of subsequences formed form s[0:i-1] that equals to t[0:j-1]
        vector<vector<long>> dp(s.size() + 1, vector<long>(t.size() + 1));
        for (int i = 0; i <= s.size(); i++) {
            dp[i][0] = 1;
        }
        for (int j = 1; j <= t.size(); j++) {
            for (int i = 1; i <= s.size(); i++) {
	        // dp[i][j] = dp[i - 1][j], if s[i - 1] != t[j - 1]
		//          = dp[i - 1][j] + dp[i - 1][j - 1], if s[i - 1] == t[j - 1]
		// Note: if s[i - 1] == t[j - 1] means that we can form t[0:j-1] from s[0:i-1] + s[i - 1] or from s[0:i-2], i.e. number of subsequences is dp[i - 1][j - 1] + dp[i - 1][j]
		// if s[i - 1] != t[j - 1], we can form t[0:j-1] "only" from s[0:i-2], i.e. number of subsequences is dp[i - 1][j]

                dp[i][j] = dp[i - 1][j] + (s[i - 1] == t[j - 1]? dp[i - 1][j - 1] : 0);    
            }
           
        }
        
        return dp[s.size()][t.size()];
    }
};

解法二(O(m) space DP):

class Solution {
public:
    int numDistinct(string s, string t) {
        // dp[i][j] means the number of subsequences formed from s[0:i-1] that equals to t[0:j-1]
        vector<long> cur(s.size() + 1); 
        cur[0] = 0;
        int pre = 1;
        for (int j = 1; j <= t.size(); j++) {
            if (j > 1) { pre = 0; }
            for (int i = 1; i <= s.size(); i++) {
                int tmp = cur[i];
		// dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1], if s[i - 1] == t[j - 1]
                cur[i] = cur[i - 1] + (s[i - 1] == t[j - 1]? pre : 0);
		// dp[i][0] = 1 for all i
                pre = (j > 1)? tmp : 1;
            }
           
        }
        
        return cur[s.size()];
    }
};