Recursion,similar to scramble string problem or LCS


#1
map<string,bool>mp;
int Solution::isInterleave(string a, string b, string c) {
   
   if(a.length()+b.length()!=c.length())return false;
   if(a.length()==0){
       return b==c;
   }
   if(b.length()==0)return a==c;
   if(c.length()==0)return false;
   
   string key=a+" "+b+" "+c;
   if(mp.find(key)!=mp.end()){
       return mp[key];
   }
   
   bool flag=false;
   if(a[0]==c[0])flag=flag||isInterleave(a.length()>1?a.substr(1):"",b,c.length()>1?
   c.substr(1):"");
   if(b[0]==c[0])flag=flag||isInterleave(a,b.length()>1?b.substr(1):"",c.length()>1?
   c.substr(1):"");
   mp[key]=flag;
   key=b+" "+a+" "+c;
   mp[key]=flag;
   
   return flag;
}