首页 > 代码库 > Distinct Subsequences
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.
方法一：假设S串为S[0...lens-1]，T串为T[0...lent-1]，从S串尾部开始往前找第一个等于T[lent-1]的字符
假设S[i] == T[lent-1]，这时原问题就分解为两个子问题，即在S[0...i-1]删除几个字符得到T[0...lent-1]及S[0...i-1]删除几个字符得到T[0...lent-2]
代码如下：
1 class Solution { 2 public: 3 int numDistinct(string S, string T) { 4 return solve(S, S.length()-1, T, T.length()-1); 5 } 6 7 int solve(string& S, int is, string& T, int it) { 8 if( it < 0 ) return 1; //当T成空串的时候，S必成空串，则T是S的distinct subsequence 9 if( is < 0 ) return 0; //T不是空串，S先成空串，那么T就不是10 while( is >= 0 && S[is] != T[it] ) --is; //S从后往前找等于T最后一个字符11 return solve(S, is-1, T, it) + solve(S, is-1, T, it-1); //原问题分解成两个子问题12 }13 };
方法二：上述递归方法求解是有很多子问题进行了重复求解，因此不能过大数据。那么可以将其转为dp问题，状态转移方程如下：
设dp[i][j]为S[0...i-1]删除字符得到T[0...j-1]的种数，那么
当S[i-1] == T[j-1]时，dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
当S[i-1] != T[j-1]时，dp[i][j] = dp[i-1][j];
当 j == 0 时，dp[i][0] = 1;
代码如下：
1 class Solution { 2 public: 3 int numDistinct(string S, string T) { 4 vector< vector<int> > dp( S.length()+1, vector<int>(T.length()+1, 0)); 5 for(int i=0; i<dp.size(); ++i) dp[i][0] = 1; //当T为空串的时候，S删除字符得到T只有一种方法 6 for(int i=1; i<dp.size(); ++i) 7 for(int j=1; j<dp[i].size(); ++j) 8 if( S[i-1] == T[j-1] ) dp[i][j] = dp[i-1][j] + dp[i-1][j-1]; //S[i-1] == T[j-1]的时候 9 else dp[i][j] = dp[i-1][j]; //不等的时候10 return dp[S.length()][T.length()];11 }12 };
Distinct Subsequences