2014.2.8 22:11
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.
Solution:
abcde
Accepted code:
1 // 2RE, 1WA, 1AC, don‘t use memset on dp[][], although it looks as if it were one block of memory. 2 #include <cstring> 3 #include <vector> 4 using namespace std; 5 6 class Solution { 7 public: 8 int numDistinct(string S, string T) { 9 int **dp; 10 int ls, lt; 11 int result; 12 int i, j; 13 14 ls = (int)S.size(); 15 lt = (int)T.size(); 16 if (ls == 0 || lt == 0) { 17 return 0; 18 } 19 20 dp = new int*[ls + 1]; 21 for (i = 0; i < ls + 1; ++i) { 22 dp[i] = new int[lt + 1]; 23 } 24 for (i = 0; i <= ls; ++i) { 25 for (j = 0; j <= lt; ++j) { 26 dp[i][j] = 0; 27 } 28 } 29 /* 30 for (i = 0; i <= ls; ++i) { 31 dp[i][0] = 0; 32 } 33 for (i = 0; i <= lt; ++i) { 34 dp[0][i] = 0; 35 } 36 */ 37 for (i = 1; i <= ls; ++i) { 38 if (S[i - 1] == T[0]) { 39 dp[i][1] = dp[i - 1][1] + 1; 40 } else { 41 dp[i][1] = dp[i - 1][1]; 42 } 43 } 44 45 for (i = 2; i <= ls; ++i) { 46 for (j = 2; j <= lt; ++j) { 47 if (S[i - 1] == T[j - 1]) { 48 dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]; 49 } else { 50 dp[i][j] = dp[i - 1][j]; 51 } 52 } 53 } 54 result = dp[ls][lt]; 55 for (i = 0; i < ls + 1; ++i) { 56 delete[] dp[i]; 57 } 58 delete[] dp; 59 dp = NULL; 60 61 return result; 62 } 63 };
LeetCode - Distinct Subsequences
原文：http://www.cnblogs.com/zhuli19901106/p/3541108.html