Posted on 2014-01-16 19:19
Uriel 阅读(169)
评论(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 }