-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathP_97.java
More file actions
38 lines (34 loc) · 1012 Bytes
/
Copy pathP_97.java
File metadata and controls
38 lines (34 loc) · 1012 Bytes
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
package leetcode.hard;
public class P_97 {
static int n;
static int m;
static int[][] dp;
static boolean[][] seen;
public boolean isInterleave(String s1, String s2, String s3) {
n = s1.length();
m = s2.length();
if (s3.length() != n + m) {
return false;
}
dp = new int[n + 1][m + 1];
seen = new boolean[n + 1][m + 1];
return dfs(s1.toCharArray(), s2.toCharArray(), s3.toCharArray(), 0, 0) > 0;
}
private static int dfs(char[] l, char[] r, char[] w, int i, int j) {
if (i + j == w.length) {
return 1;
}
if (seen[i][j]) {
return dp[i][j];
}
int res = 0;
if (i < l.length && l[i] == w[i + j]) {
res = Math.max(res, dfs(l, r, w, i + 1, j));
}
if (j < r.length && r[j] == w[i + j]) {
res = Math.max(res, dfs(l, r, w, i, j + 1));
}
seen[i][j] = true;
return dp[i][j] = res;
}
}