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
.
简单DP,一次写过,还不错~ 就是写的时候发现滚动数组写得还是不太熟。
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]; } };