forked from walnutown/CodingInTheDeep
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathDistinctSubsequence.java
More file actions
74 lines (69 loc) · 2.38 KB
/
Copy pathDistinctSubsequence.java
File metadata and controls
74 lines (69 loc) · 2.38 KB
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
/*
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.
*/
// DFS
// TLE
public class Solution {
public int numDistinct(String S, String T) {
if (S==null || T==null) return 0;
int[] num = new int[1];
finder(S.toCharArray(), 0, T.toCharArray(), 0, num);
return num[0];
}
public void finder(char[] s, int i, char[] t, int j, int[] num){
if (j==t.length){
num[0]++;
return;
}
if (i==s.length) return;
for (int k=i; k<s.length; k++){
if (s[k] != t[j]) continue;
finder(s, i+1, t, j+1, num);
}
}
}
// 2d DP, http://blog.csdn.net/u011095253/article/details/9248121
// dp[i][j] = dp[i][j-1] + dp[i-1][j-1], delete the char, or include the char
public class Solution {
public int numDistinct(String S, String T) {
if (S==null || T==null) return 0;
int m=T.length(), n=S.length();
int[][] dp = new int[m+1][n+1];
dp[0][0] = 1;
for (int i=1; i<=m; i++) dp[i][0] = 0;
for (int j=1; j<=n; j++) dp[0][j] = 1;
for (int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
if (T.charAt(i-1) == S.charAt(j-1)) dp[i][j] = dp[i][j-1] + dp[i-1][j-1];
else dp[i][j] = dp[i][j-1];
}
}
return dp[m][n];
}
}
// 1d DP, remember the conditions of transform 2d DP to 1d DP, and how to transfrom
public class Solution {
public int numDistinct(String S, String T) {
if (S==null || T==null) return 0;
int m=T.length(), n=S.length();
int[] dp = new int[n+1];
for (int j=0; j<=n; j++) dp[j] = 1;
for (int i=1; i<=m; i++){
int prev = dp[0];
dp[0] = 0;
for(int j=1; j<=n; j++){
int tmp = dp[j];
if (T.charAt(i-1) == S.charAt(j-1)) dp[j] = dp[j-1] + prev;
else dp[j] = dp[j-1];
prev = tmp;
}
}
return dp[n];
}
}