-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathDp392.java
More file actions
55 lines (51 loc) · 1.58 KB
/
Dp392.java
File metadata and controls
55 lines (51 loc) · 1.58 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
package dynamicprogramming;
public class Dp392 {
public boolean isSubsequence(String s, String t) {
if (s.length() == 0) {
return true;
}
if (t.length() == 0) {
return false;
}
boolean[][] dp = new boolean[s.length()][t.length()];
dp[0][0] = s.charAt(0) == t.charAt(0);
for (int i = 1; i < t.length(); i++) {
dp[0][i] = s.charAt(0) == t.charAt(i) || dp[0][i-1];
}
for (int i = 1; i < s.length(); i++) {
dp[i][0] = false;
}
for (int i = 1; i < s.length(); i++) {
for (int j = 1; j < t.length(); j++) {
if (s.charAt(i) == t.charAt(j)) {
dp[i][j] = dp[i-1][j-1];
} else {
dp[i][j] = dp[i][j-1];
}
}
}
return dp[s.length()-1][t.length()-1];
}
/**
* Runtime: 17 ms, faster than 46.85% of Java online submissions for Is Subsequence.
* Memory Usage: 48.2 MB, less than 100.00% of Java online submissions for Is Subsequence.
* @param s
* @param t
* @return
*/
public boolean isSubsequence2(String s, String t) {
if (s.length() == 0) {
return true;
}
int sIndex = 0, tIndex;
for (tIndex = 0; sIndex < s.length() && tIndex < t.length(); tIndex++) {
if (s.charAt(sIndex) == t.charAt(tIndex)) {
sIndex ++;
}
if (sIndex == s.length()) {
return true;
}
}
return false;
}
}