The idea is to try every solutions (sounds like a brute force method) and keep (memoize) them in the HashMap. If we already save the solution, we won't compute it again, thus saving time.

```
public boolean isInterleave(String s1, String s2, String s3) {
if(s1.length()+s2.length() != s3.length())
return false;
HashMap<String, Boolean> hm = new HashMap<String, Boolean>();
hm.put(",", true);
return isInterleave(s1, s2, s3, hm);
}
private boolean isInterleave(String s1, String s2, String s3, HashMap<String, Boolean> hm) {
String temp = s1+","+s2;
if(hm.containsKey(temp))
return hm.get(temp);
boolean left = false, right= false;
if(s1.length()!=0 && s1.charAt(0)==s3.charAt(0))
left = isInterleave(s1.substring(1), s2, s3.substring(1), hm);
if(s2.length()!=0 && s2.charAt(0)==s3.charAt(0))
right = isInterleave(s1, s2.substring(1), s3.substring(1), hm);
hm.put(temp, left||right);
return left||right;
}
```