[LeetCode OJ] Distinct Subsequences

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

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).

Here is an example:

S = 

"rabbbit"

, T = 

"rabbit"

Return 

3

.

方法一：用回溯法實作，時間複雜度很高，空間複雜度低，對于小資料可以通過，對大資料會出現Time Limit Exceeded

1 int num=0;
 2 void countnum(string S, string T) {
 3     if(T.size()==0)
 4     {
 5         num++;
 6         return;
 7      }
 8            
 9      for(int i=0; i<S.size(); i++)
10      {
11          if(S[i]==T[0])
12          {
13              string s2 = S.substr(i+1);
14              string t2 = T.substr(1);
15               countnum(s2, t2);
16           }
17               
18      }
19      return;
20 }
21 
22 class Solution {
23 public:
24     int numDistinct(string S, string T) {
25         countnum(S, T);
26         return num;
27     }
28 };      

方法二：用動态規劃（DP）實作，需要的空間複雜度為O(N*M)，對于大資料也可以很快處理。

1 class Solution {
 2 public:
 3     int numDistinct(string S, string T) {
 4         vector<vector<int> > num(S.size()+1,vector<int>(T.size()+1,0)); //num[i][j]表示T中的前j個字元構成的子字元串在S中的前i個字元中出現的次數,num[i][j]滿足:
 5         S = " "+ S;                                                                                 //（1）若S[i]=T[j]，則num[i][j] = num[i-1][j]+num[i-1][j-1]；
 6         T = " "+ T;                                                                                 //（2）若S[i]!=T[j]，則num[i][j] = num[i-1][j]；
 7         num[0][0]=1;                                                                                //（3）若j>i，則num[i][j]=0。
 8         for(int i=1; i<S.size(); i++)
 9             for(int j=0; j<T.size(); j++)
10             {
11                 if(j>i)
12                 {
13                     num[i][j]=0;
14                     break;
15                 }
16                 if(S[i]==T[j])
17                     num[i][j] = num[i-1][j] + num[i-1][j-1];
18                 else
19                     num[i][j] = num[i-1][j];
20             }
21             return num[S.size()-1][T.size()-1];
22 
23     }
24 };      

轉載于:https://www.cnblogs.com/Marrybe/p/3788507.html