// You can also solve it with making substrings at each step, but it is slower.
// Current solution runs in 3ms and beats 85.36%
public class Solution {
  public boolean isInterleave(String s1, String s2, String s3) {
    if (s1.length() + s2.length() != s3.length()) return false;
    return recur(s1, 0, s2, 0, s3, 0, new HashMap<String, Boolean>());
  }

  private boolean recur(String s1, int i, String s2, int j, String s3, int k, HashMap<String, Boolean> memo) {
    if (s1.length() == i && s2.length() == j && s3.length() == k) return true;
    if (s3.length() == k) return false;
    String key = i + "-" + j + "-" + k;
    if (memo.containsKey(key)) return memo.get(key);
    char a = s3.charAt(k);
    boolean flag = false;
    if (s1.length() > i && s1.charAt(i) == a) {
      flag = flag || recur(s1, i + 1, s2, j, s3, k + 1, memo);
    }
    if (!flag && s2.length() > j && s2.charAt(j) == a) {
      flag = flag || recur(s1, i, s2, j + 1, s3, k + 1, memo);
    }
    memo.put(key, flag);
    return flag;
  }
}

@@ -101,17 +101,17 @@
 runs in 
-3
+1
 ms and b
@@ -119,13 +119,13 @@
 ats 
-85.36
+91.83
 %25%0Apu
@@ -271,24 +271,86 @@
 turn false;%0A
+    int%5B%5D%5B%5D memo = new int%5Bs1.length() + 1%5D%5Bs2.length() + 1%5D;%0A
     return r
@@ -379,38 +379,12 @@
  0, 
-new HashMap%3CString, Boolean%3E()
+memo
 );%0A 
@@ -469,32 +469,15 @@
  k, 
-HashMap%3CString, Boolean%3E
+int%5B%5D%5B%5D
  mem
@@ -608,73 +608,27 @@
     
-String key = i + %22-%22 + j + %22-%22 + k;%0A    if (memo.containsKey(key)
+if (memo%5Bi%5D%5Bj%5D != 0
 ) re
@@ -640,17 +640,19 @@
 memo
-.get(key)
+%5Bi%5D%5Bj%5D == 1
 ;%0A  
@@ -702,32 +702,36 @@
  false;%0A    if (
+i %3C 
 s1.length() %3E i 
@@ -729,12 +729,8 @@
 th()
- %3E i
  && 
@@ -742,32 +742,34 @@
 arAt(i) == a) %7B%0A
+  
       flag = fla
@@ -837,16 +837,20 @@
 !flag &&
+ j %3C
  s2.leng
@@ -857,12 +857,8 @@
 th()
- %3E j
  && 
@@ -874,24 +874,26 @@
 (j) == a) %7B%0A
+  
       flag =
@@ -961,23 +961,30 @@
 memo
-.put(key, flag)
+%5Bi%5D%5Bj%5D = flag ? 1 : -1
 ;%0A  

improve solution