Leetcode-115. Distinct Subsequences

Given a string S and a string T, count the number of distinct subsequences of S which equals T.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, 

"ACE"

 is a subsequence of 

"ABCDE"

 while 

"AEC"

 is not).

Example 1:

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                
^^^ ^^^
      

Example 2:

Input: S =          "babgbag"                , T =          "bag"
Output: 5
                Explanation:

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

         babgbag                
^^ ^
         babgbag                
^^    ^
         babgbag                
^    ^^
         babgbag                
  ^  ^^
         babgbag                
    ^^^
      

Accepted

98,590

Submissions

287,652

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

此題為hard難度，其解法類似與算法課上的找最長字串，而這裡是找在S中有幾個T子串。實際上就是用DP方法去維護一個二維數組，這個數組的的dp[i][j]就是對于t[0~i]和s[0~j]的此題的解。（也就是在此時s中有多少個t子串）。然後通過動态規劃的化解可以知道，dp[i][j]=dp[i][j-1]（如果兩個串最後一個值不相等)，dp[i][j]=dp[i-1][j-1]+dp[i][j-1]（如果最後一個值相等）再根據初始值和邊值條件，對數組進行周遊指派，以得最後的解。