LeetCode第115題--不同的子序列

給定一個字元串 S 和一個字元串 T，計算在 S 的子序列中 T 出現的個數。

一個字元串的一個子序列是指，通過删除一些（也可以不删除）字元且不幹擾剩餘字元相對位置所組成的新字元串。（例如，“ACE” 是 “ABCDE” 的一個子序列，而 “AEC” 不是）

示例 1:

輸入: S = “rabbbit”, T = “rabbit”

輸出: 3

解釋:

如下圖所示, 有 3 種可以從 S 中得到 “rabbit” 的方案。

(上箭頭符号 ^ 表示選取的字母)

rabbbit

^^^^ ^^

rabbbit

^^ ^^^^

rabbbit

^^^ ^^^

示例 2:

輸入: S = “babgbag”, T = “bag”

輸出: 5

解釋:

如下圖所示, 有 5 種可以從 S 中得到 “bag” 的方案。

(上箭頭符号 ^ 表示選取的字母)

babgbag

^^ ^

babgbag

^^ ^

babgbag

^ ^^

babgbag

^ ^^

babgbag

^^^

class Solution {
public:
    int numDistinct(string s, string t) {
        if(s.length() == 0 || t.length() == 0) return 0;
        int sLen = s.length();
        int tLen = t.length();
        //dp[i][j]代表字元串s的第1--i個字元中含有字元串t的1--j個字元的次數
        vector<vector<long>> dp(sLen+1, vector<long>(tLen+1, 0));  這裡采用long型，否則用例會超出記憶體
        for(int i = 0; i <= sLen; i++)
        {
            dp[i][0] = 1;						//注意此處初始化為1		
        }
        for(int j = 1; j <= tLen; j++)
        {
            for(int i = j; i <= sLen; i++)
            {
                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[sLen][tLen];
    }
};
           

參考思路如下：

• 設dp[i][j]表示s[0:i-1]的子序列中t[0:j-1]出現的次數，則
             

• 1.若s[i-1] == t[j-1] => dp[i][j] = dp[i-1][j-1] (用s[i-1]與t[j-1]配對) + dp[i-1][j](抛棄s[i-1],不用s[i-1]與t[j-1]配對)
             

• 2.若s[i-1] != t[j-1] => dp[i-1][j] (直接抛棄s[i-1],不用s[i-1]與t[j-1]配對)