PROBLEM DESCRIPTION
Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2.
An interleaving of two strings s and t is a configuration where s and t are divided into n and m substrings respectively, such that:
1
2
3
4
s = s1 + s2 + ... + sn
t = t1 + t2 + ... + tm
|n - m| <= 1
The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + ... or t1 + s1 + t2 + s2 + t3 + s3 + ...
SOLUTION
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
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if(s1.length() + s2.length() != s3.length()) return false;
return check(s1, s2, s3, 0, 0, 0, new HashMap<String, Boolean>());
}
public boolean check(String s1, String s2, String s3, int i, int j, int k, Map<String, Boolean> map){
//we have parsed all characters in s3
//return true, because they must have matches some character in s1 or s2
if(k == s3.length()){
return true;
}
if(!map.containsKey(i+":"+j)){
boolean possible = false;
//no characters in s1 remaining to be parsed
if(i == s1.length()){
if(s3.charAt(k) == s2.charAt(j)){
possible = check(s1, s2, s3, i, j+1, k+1, map);
map.put(i+":"+j, possible);
return possible;
}else{
return false;
}
}
//no characters in s2 remaining to be parsed
if(j == s2.length()){
if(s3.charAt(k) == s1.charAt(i)){
possible = check(s1, s2, s3, i+1, j, k+1, map);
map.put(i+":"+j, possible);
return possible;
}else{
return false;
}
}
boolean o1 = false;
boolean o2 = false;
if(s3.charAt(k) == s1.charAt(i)){
o1 = check(s1, s2, s3, i+1, j, k+1, map);
}
if(s3.charAt(k) == s2.charAt(j)){
o2 = check(s1, s2, s3, i, j+1, k+1, map);
}
map.put(i+":"+j, o1 || o2);
}
return map.get(i+":"+j);
}
}