Distinct Subsequences

发布时间:2017-3-27 8:47:08 编辑: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)
下一篇:阿里巴巴数据库操作手册-20-固定执行计划-outline

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款