Skip to content

Commit bddcebe

Browse files
HARD/src/hard/InterleavingString.java
1 parent 887025a commit bddcebe

File tree

1 file changed

+44
-0
lines changed

1 file changed

+44
-0
lines changed

HARD/src/hard/InterleavingString.java

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
package hard;
2+
3+
public class InterleavingString {
4+
public boolean isInterleave(String s1, String s2, String s3) {
5+
// write your code here
6+
int m = s1.length(), n = s2.length();
7+
if(m+n != s3.length()) return false;
8+
9+
boolean[][] dp = new boolean[m+1][n+1];
10+
11+
dp[0][0] = true;
12+
13+
for(int i = 0; i < m; i++){
14+
if(s1.charAt(i) == s3.charAt(i)){
15+
dp[i+1][0] = true;
16+
}
17+
else {//if one char fails, that means it breaks, the rest of the chars won't matter any more.
18+
//Mian and I found one missing test case on Lintcode: ["b", "aabccc", "aabbbcb"]
19+
//if we don't break, here, Lintcode could still accept this code, but Leetcode fails it.
20+
21+
break;
22+
}
23+
}
24+
25+
for(int j = 0; j < n; j++){
26+
if(s2.charAt(j) == s3.charAt(j)){
27+
dp[0][j+1] = true;
28+
}
29+
else {
30+
break;
31+
}
32+
}
33+
34+
for(int i = 1; i <= m; i++){
35+
for(int j = 1; j <= n; j++){
36+
int k = i+j-1;
37+
dp[i][j] = (s1.charAt(i-1) == s3.charAt(k) && dp[i-1][j])
38+
|| (s2.charAt(j-1) == s3.charAt(k) && dp[i][j-1]);
39+
}
40+
}
41+
42+
return dp[m][n];
43+
}
44+
}

0 commit comments

Comments
 (0)