首页 > 代码库 > 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.
思路：遍历T，依次确定满足T[0],T[1],...T[m]的元素S[i]的位置(即i)和路径数。满足T[j]的元素必然出现在某个满足T[j-1]的元素之后，且其路径数为该满足T[j-1]的元素及其之前出现的所有满足T[j-1]的元素的路径数之和。最后，将满足T[m]的所有元素的路径数加和即为所求。
1 class Solution { 2 public: 3 int numDistinct( string S, string T ) { 4 int slen = S.length(), tlen = T.length(); 5 if( tlen == 0 ) { return 1; } 6 if( slen < tlen ) { return 0; } 7 vector<pair<int,int>> idxCnt( 2, make_pair( -1, 1 ) ); 8 idxCnt.back().first = slen-tlen; 9 for( int index = 0; index < tlen; ++index ) {10 vector<pair<int,int>> newIdxCnt;11 for( size_t i = 1; i != idxCnt.size(); ++i ) {12 for( int k = idxCnt[i-1].first+1; k <= idxCnt[i].first; ++k ) {13 if( S[k] != T[index] ) { continue; }14 newIdxCnt.push_back( make_pair( k, idxCnt[i-1].second ) );15 }16 idxCnt[i].second += idxCnt[i-1].second;17 }18 if( newIdxCnt.empty() ) { return 0; }19 newIdxCnt.push_back( idxCnt.back() );20 idxCnt = newIdxCnt;21 ++idxCnt.back().first;22 }23 int numDist = 0;24 for( size_t i = 1; i != idxCnt.size(); ++i ) {25 numDist += idxCnt[i-1].second;26 }27 return numDist;28 }29 };
上述算法的思路还是比较清晰的。不过，要描述清楚却实在是费劲，实现起来也比较麻烦。我们来看网上基于DP的算法：
numDist[i][j]表示S(0:i)经过删除字符变到T(0:j)的方法数。若S[i]==T[j]，有numDist[i][j] = numDist[i-1][j-1] + numDist[i-1][j]；若S[i]!=T[j]，则numDist[i][j] = numDist[i-1][j]。
1 class Solution { 2 public: 3 int numDistinct( string S, string T ) { 4 int sLen = S.length(), tLen = T.length(); 5 if( sLen < tLen ) { return 0; } 6 vector<vector<int>> numDist( sLen+1, vector<int>( tLen+1, 0 ) ); 7 for( int i = 1; i <= sLen; ++i ) { 8 numDist[i-1][0] = 1; 9 for( int j = 1; j <= tLen; ++j ) {10 if( S[i-1] != T[j-1] ) {11 numDist[i][j] = numDist[i-1][j];12 } else {13 numDist[i][j] = numDist[i-1][j-1] + numDist[i-1][j];14 }15 }16 }17 return numDist[sLen][tLen];18 }19 };