/
Solution.java
71 lines (67 loc) · 2.4 KB
/
Solution.java
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
/**
* Time : O(N^2); Space: O(N^2)
* @tag : Dynamic Programming; String
* @by : Steven Cooks
* @date: Jun 16, 2015
********************************************************
* Description:
*
* 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.
*
********************************************************
* {@link https://leetcode.com/problems/distinct-subsequences/ }
*/
package _115_DistinctSubsequences;
/** see test {@link _115_DistinctSubsequences.SolutionTest } */
public class Solution {
public int numDistinct(String s, String t) {
int[][] dp = new int[s.length() + 1][t.length() + 1];
for (int i = s.length(); i >= 0; i--) {
for (int j = t.length(); j >= 0; j--) {
int count = 0;
if (i == s.length() && j == t.length()) {
count = 1;
} else if (i == s.length()) {
count = 0;
} else if (j == t.length()) {
count = 1;
} else if (s.charAt(i) != t.charAt(j)) {
count = dp[i + 1][j];
} else {
count = dp[i + 1][j] + dp[i + 1][j + 1];
}
dp[i][j] = count;
}
}
return dp[0][0];
}
public int numDistinct2(String s, String t) {
int[][] dp = new int[s.length() + 1][t.length() + 1];
for (int i = s.length(); i >= 0; i--) {
for (int j = t.length(); j >= 0; j--) {
int count = 0;
if (i == s.length() && j == t.length()) {
count = 1;
} else if (i == s.length()) {
count = 0;
} else if (j == t.length()) {
count = 1;
} else if (s.charAt(i) != t.charAt(j)) {
count = dp[i + 1][j];
} else {
count = dp[i + 1][j] + dp[i + 1][j + 1];
}
dp[i][j] = count;
}
}
return dp[0][0];
}
}