Solution with help of map


#1

map<string,bool>mp;
bool soln(string A,string B)
{
int n=A.length();
int m=B.length();
if(A==B)
{
return 1;
}
if(A.length()<=1)
{
return 0;
}
string key=A;
key.push_back(’_’);
key.append(B);
if(mp.find(key)!=mp.end())
{
return mp[key];
}
bool flag=false;
int len=A.length();
for(int i=1;i<A.length();i++)
{
if((soln(A.substr(0,i),B.substr(0,i))&&soln(A.substr(i),B.substr(i)))||(soln(A.substr(0,i),B.substr(len-i))&&soln(A.substr(i),B.substr(0,len-i))))
{
flag=true;
}

}
mp[key]=flag;
return mp[key];

}
int Solution::isScramble(const string A, const string B)
{
mp.clear();
return soln(A,B);


#2

Hey Nikhil ca n you please help me with this it is getting tle
unordered_map<string, bool> mp;

bool solve(string A,string B){
int n=A.length();

 if(A==B) {return true;}
 if(n<=1) return false;
// int i=0,j=n-1;
 string temp=A+"_"+B;
 
 if(mp.find(temp)!=mp.end()) return mp[temp];
 bool flag=false;
 for(int k=1;k<=n-1;k++){
    if((solve(A.substr(0,k),B.substr(n-k,k)) and solve(A.substr(k,n-k),B.substr(0,n-k))) or (solve(A.substr(0,k),B.substr(0,k)) and solve(A.substr(k,n-k),B.substr(k,n-k)))) 
                {flag=true;break;} }
 return flag;

}

int Solution::isScramble(const string A, const string B) {
// mp.clear();

 return solve(A,B);

}


#3

mp[temp]=flag; //ADD THIS ALSO
return flag;