Posted on 2014-01-16 19:19
Uriel 閱讀(197)
評論(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 }