# C++ AC code using recursion and hash-map

• Idea:

(str1,str2) is a scramble pair when :

1. there exist an i, such that both (str1[0:i],str2[0:i]) and (str[i:end],str[i:end]) are scramble pairs;
or
2. there exist an i, such that both (str1[0:i],str2[i:end]) and (str[i:end],str[0:i]) are scramble pairs;

once str1 and str2 are determined, hash_map[str1+str2] can be set to the flag, as well as hash_map[str2+str1]

some acceleration can be added before recurse such as check whether s1==s2 and hist[s1]==hist[s2];

``````class Solution {
public:
unordered_map <string,bool> map;
bool isScramble(string s1, string s2) {
int n = s1.length();
if(n!=s2.length()) return false;
if(n==1) return s1[0]==s2[0];
if(s1==s2) return true;
bool comp = false;
if(map.count(s1+s2)>0)
{
comp = map[s1+s2];
}
else
{
int hist1[128]={0};
int hist2[128]={0};
for(int i = 0; i<n; i++)
{
hist1[s1[i]]++;
hist2[s2[i]]++;
}
comp = true;
for(int i = 0; i<128; i++)
{
if(hist1[i]!=hist2[i])
{
comp = false;
break;
}
}
if(comp)
for(int i = 1; i<n; i++)
{
comp = isScramble(s1.substr(0,i),s2.substr(n-i,i));
comp = comp && isScramble(s1.substr(i),s2.substr(0,n-i));
bool comp1 = isScramble(s1.substr(0,i),s2.substr(0,i));
comp1 = comp1 && isScramble(s1.substr(i),s2.substr(i));
comp = comp || comp1;
if(comp) break;
}
map[s1+s2]=comp;
map[s2+s1]=comp;
}
//cout<<s1<<"|"<<s2<<"|"<<comp<<endl;
return comp;
}
};``````

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