Distinct Subsequences

发布时间:2017-1-24 9:02:14 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"Distinct Subsequences",主要涉及到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. 方法 :动态规划dist[i][j]为S[1,i]包含T[1,j]作为子串的种类数。则递推公式: S[i][j] =     S[i-1][j]                              (S[i] != T[j])  不使用S[i],S[1,i-1]中包含T[1,j]的子串数                  S[i-1][j-1] + S[i-1][j]          (S[i] == T[j])  使用S[i],S[1,i-1]中包含T[1,j-1]的子串数和 不使用S[i],,S[1,i-1]中包含T[1,j]的子串数的和。 class Solution { public: int numDistinct(string S, string T) { // Start typing your C/C++ solution below // DO NOT write int main() function int n = S.length(); int m = T.length(); int dist[n+1][m+1]; for(int i = 0; i<=n;i++) dist[i][0] = 1; for(int j = 1; j<=m;j++) dist[0][j] = 0; for(int i = 1;i<=n;i++) { for(int j = 1;j<=m;j++) { if(S[i-1] == T[j-1]){ dist[i][j] = dist[i-1][j-1] + dist[i-1][j]; }else{ dist[i][j] = dist[i-1][j]; } } } return dist[n][m]; } };40 milli secs.

上一篇:Oracle ACL(Access Control List)