Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

[LeetCode]Distinct Subsequences-2014.01.16

Posted on 2014-01-16 19:19 Uriel 阅读(177) 评论(0)  编辑 收藏 引用 所属分类: LeetCode
给两个字符串A和B,求A中B出现几次(不需要匹配连续字符)
明显的LCS扩展,虽然还是搞了很久,RE一次数组开太小,以后看这种直接滚动数组。。

 1 int dp[2][122010];
 2 int numDistinct(string S, string T) {
 3     int res = 0;
 4     memset(dp, 0, sizeof(dp));
 5     dp[0][0] = dp[1][0] = 1;
 6     for(int i = 1; i <= S.length(); ++i) {
 7         for(int j = 1; j <= T.length(); ++j) {
 8             if(S[i - 1] == T[j - 1]) {
 9                 dp[i & 1][j] = dp[(i - 1) & 1][j - 1] + dp[(i - 1) & 1][j];
10             }
11             else
12                 dp[i & 1][j] = dp[(i - 1) & 1][j];
13         }
14     }
15     return dp[S.length() & 1][T.length()];
16 }

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理