LeetCode/DistinctSubsequences.cpp at master · Riddance/LeetCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
public:
    int numDistinct(string S, string T) {
    	int m = S.size();
    	int n = T.size();

    	if (m < n) {
    		return 0;
    	}

    	vector<vector<int> > result(m + 1, vector<int>(n + 1, 0));
    	for (int i = 0; i <= m; ++i) {
    		result[i][0] = 1;
    	}

    	for (int i = 1; i <= m; ++i) {
    		for (int j = 1; j <= n; ++j) {
    			result[i][j] = result[i - 1][j];
    			if (S[i - 1] == T[j - 1]) {
    				result[i][j] += result[i - 1][j - 1];
    			}
    		}
    	}

    	return result[m][n];
    }
};


//this Solution will TLE
class Solution {
public:
    int numDistinct(string S, string T) {
    	int num = 0;

    	if (T.size() == 0) {
    		num = 1;
    		goto out;
    	}

    	if (S.size() == 0) {
    		goto out;
    	}

    	for (int i = 0; i < S.size(); ++i) {
    		if (S[i] == T[0]) {
    			num += numDistinct(S.substr(i + 1), T.substr(1));
    		}
    	}

    	out:
    	return num;
  }
};