首页 > 代码库 > Distinct Subsequences
Distinct Subsequences
https://leetcode.com/problems/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
.
定义f[i][j]表示在S[0,i]中,T[0,j]出现了几次。无论s[i]和t[j]是否相等,如果不匹配s[i],则f[i][j]=f[i-1][j];若s[i]==s[j],
f[i][j]=f[i-1][j]+[i-1][j-1]。
另外,当t=""时,只有一种匹配方式,f[i][0]=1;当s="",t!=""时,无论如何无法匹配,此时f[0][j]=0。
参考:http://www.cnblogs.com/yuzhangcmu/p/4196373.html
int numDistinct(string s, string t) { int m=s.size(); int n=t.size(); vector<vector<int>> f(m+1,vector<int>(n+1,0)); for(int i=0;i<=m;i++) { for(int j=0;j<=n;j++) { if(i==0 && j==0) f[i][j]=1; else if(i==0) f[i][j]=0; else if(j==0) f[i][j]=1; else f[i][j]=f[i-1][j]+(s[i-1]==t[j-1]?f[i-1][j-1]:0); } } return f[m][n]; }
Distinct Subsequences