A simple derivation of MCM, doesn't even deserve 500 points

programming
Tags: #<Tag:0x00007f2445e7e580>

#1
 map<pair<string,string>,bool>cache;
 int dp(const string&a,const string&b)
 {if(a.size()!=b.size()){return false;}
 pair<string,string>p={a,b};
 if(cache.find(p)!=cache.end()){
return cache[p];}
string temp1=a,temp2=b;
sort(temp1.begin(),temp1.end());
sort(temp2.begin(),temp2.end());
if(temp1.compare(temp2)!=0){return false;}
if(temp1.size()<=2){return true;}
for(int i=1;i<a.size();i++)
{if(dp(a.substr(0,i),b.substr(0,i))&&dp(a.substr(i),b.substr(i)))
{return cache[p]=true;}
if(dp(a.substr(0,i),b.substr(b.size()-i))&&dp(a.substr(i),b.substr(0,b.size()-i)))
{return cache[p]=true;}}
return cache[p]=false;}
   
int Solution::isScramble(const string s1, const string s2) {
    if(s1.length()!=s2.length()) return false;
    cache.clear();
        return dp(s1,s2);
}