Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
Example 1:
1
2
| Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
|
Example 2:
1
2
| Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false
|
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
| class Solution(){
public boolean isInterleave(String s1, String s2, String s3) {
if (s1.length() + s2.length() != s3.length()){
return false;
}
boolean[][] matrix = new boolean[s1.length()+1][s2.length()+1];
matrix[0][0] = true;
for (int i=1; i<s1.length()+1; i++){
if (s3.charAt(i-1) == s1.charAt(i-1) && matrix[i-1][0]){
matrix[i][0] = true;
}
}
for (int i=1; i<s2.length()+1; i++){
if (s3.charAt(i-1) == s2.charAt(i-1) && matrix[0][i-1]){
matrix[0][i] = true;
}
}
for (int i=1; i<s1.length()+1; i++){
for (int j=1; j<s2.length()+1; j++){
if (s3.charAt(i+j-1) == s1.charAt(i-1) && matrix[i-1][j]){
matrix[i][j] = true;
}
if (s3.charAt(i+j-1) == s2.charAt(j-1) && matrix[i][j-1]){
matrix[i][j] = true;
}
}
}
return matrix[s1.length()][s2.length()];
}
}
|
