# Recursive and cache solution. (C++ 4ms)

• ``````class Solution {
unordered_map<int, bool> cache;

int hashCode(int x, int y) {
return x * 100007 + y;
}
public:
bool isInterleave(string s1, string s2, string s3) {
cache.clear();
if (s1.length() + s2.length() != s3.length()) return false;
return Core(s1, 0, s2, 0, s3);
}

bool Core(string& s1, int index1, string& s2, int index2, string& s3) {
int hash = hashCode(index1, index2);
if (cache.find(hash) == cache.end()) {
int i = index1 + index2;
const int length = s3.length();
for (; i < length; i++) {
if (index1 == s1.length() && index2 == s2.length()) {
break;
} else if (index1 == s1.length()) {
if (s2[index2++] != s3[i]) break;
} else if (index2 == s2.length()) {
if (s1[index1++] != s3[i]) break;
} else if (s1[index1] != s2[index2]) {
if (s1[index1] == s3[i]) index1++;
else if (s2[index2] == s3[i]) index2++;
else break;
} else {
if (s1[index1] != s3[i]) break;
if (Core(s1, index1+1, s2, index2, s3)) { cache[hash] = true; return true; }
if (Core(s1, index1, s2, index2+1, s3)) { cache[hash] = true; return true; }
break;
}
}
if (i == length) cache[hash] = true;
else cache[hash] = false;
}
return cache[hash];
}
``````

};

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.