```
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
return isInterleave(s1, 0, s2, 0, s3,0);
}
private:
bool isInterleave(string& s1, int i , string& s2, int j, string& s3, int k){
if(Map.count(make_tuple(i,j,k))) return Map[make_tuple(i,j,k)];
if(k==s3.size()){ // we have completed the s3
return(i==s1.size() && j==s2.size()); // they both should be finished
}
bool option1=((i<s1.size() && s1[i]==s3[k])&&isInterleave(s1,i+1,s2,j,s3,k+1));
bool option2=((j<s2.size() && s2[j]==s3[k])&&isInterleave(s1,i,s2,j+1,s3,k+1));
return Map[make_tuple(i,j,k)]=(option1 || option2);
}
map<tuple<int,int,int>, bool> Map;
};
```