public class Solution {
Set<String> mem = new HashSet<String>();
public boolean isInterleave(String s1, String s2, String s3) {
if(s1.length() == 0 && s2.length() == 0 && s3.length() == 0)
return true;
if(mem.contains(s1+"#"+s2))
return false;
if(s3.length() > 0){
if(s1.length() > 0 && s1.charAt(0) == s3.charAt(0))
if(isInterleave(s1.substring(1),s2,s3.substring(1))) return true;
if(s2.length() > 0 && s2.charAt(0) == s3.charAt(0))
if(isInterleave(s1,s2.substring(1),s3.substring(1))) return true;
}
mem.add(s1+"#"+s2);
return false;
}
}
4ms recursive java


Without the memoization, the runtime is O(2^(m+n)), where m and n are lengths of s1 and s2 respectively. With memoization, I believe it is O(m.n) because there are m*n possible substrings of s1 and s2. Therefore the function isInterleave can only be executed for a maximum of m*n times. To see why there are only m*n substrings, I have replaced the lines "mem.contains(s1+s3+s2)" and "mem.add(s1+s3+s2);" to mem.contains(s1+"#"+s2) and "mem.add(s1+"#"+s2);" respectively.

@band said in 4ms recursive java:
if(mem.contains(s1+"#"+s2))
Nice solution! I used to use DP way to address it. But I'd like to try different ways.
Here I don`t understand this: s1+"#"+s2. What does it mean? Could you explain it? Thank you.

@sshen8734
I am just memorizing that the string 's1 + "#" + s2' is not a valid interleaving of s3. The reason I am having a "#" is to separate the cases 1) "s1 = aa" and "s2 = a" and 2) "s1=a" and "s2=aa". But it may not be necessary.