## [LeetCode] Distinct Subsequences

2017年12月23日 ⁄ 综合 ⁄ 共 827字 ⁄ 字号 评论关闭

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

```class Solution {
public:
int numDistinct(string S, string T) {
// Start typing your C/C++ solution below
// DO NOT write int main() function

int ns=S.length(),nt=T.length();
if (ns < nt )
return 0;
vector<vector<int> > dp(2,vector<int>(nt+1,0));
dp[0][0]=1;
for(int i=1;i<=ns;i++)
{
vector<int>& cur =dp[i%2];
vector<int>& pre =dp[(i-1)%2];
cur[0]=1;
for(int j=1;j<=nt;j++)
{
if ( i < j )
break;
if ( S[i-1]==T[j-1] )
cur[j]=pre[j-1]+pre[j];
else
cur[j]=pre[j];
}
}
return dp[ns%2][nt];
}
};
```