# My C++ solutions (recursion with cache , DP, recursion with cache and pruning) with explanation (4ms)

• The basic idea is to divide s1(s2) into two substrings with length k and len-k and check if the two substrings s1[0..k-1] and s1[k, len-1] are the scrambles of s2[0..k-1] and s2[k,len-1] or s2[len-k, len-1] and s2[0..len-k-1] via recursion. The straigtforward recursion will be very slow due to many repeated recursive function calls. To speed up the recursion, we can use an unordered_map isScramblePair to save intermediate results. The key used here is s1+s2, but other keys are also possible (e.g. using indices)

``````    class Solution {
bool DP_helper(unordered_map<string, bool> &isScramblePair, string s1, string s2)
{
int i,len = s1.size();
bool res = false;
if(0==len) return true;
else if(1==len) return s1 == s2;
else
{
if(isScramblePair.count(s1+s2)) return isScramblePair[s1+s2]; // checked before, return intermediate result directly
if(s1==s2) res=true;
else{
for(i=1; i<len && !res; ++i)
{
//check s1[0..i-1] with s2[0..i-1] and s1[i..len-1] and s2[i..len-1]
res = res || (DP_helper(isScramblePair, s1.substr(0,i), s2.substr(0,i)) && DP_helper(isScramblePair, s1.substr(i,len-i), s2.substr(i,len-i)));
//if no match, then check s1[0..i-1] with s2[len-k.. len-1] and s1[i..len-1] and s2[0..len-i]
res = res || (DP_helper(isScramblePair, s1.substr(0,i), s2.substr(len-i,i)) && DP_helper(isScramblePair, s1.substr(i,len-i), s2.substr(0,len-i)));
}
}
return isScramblePair[s1+s2]= res; //save the intermediate results

}
}
public:
bool isScramble(string s1, string s2) {
unordered_map<string, bool> isScramblePair;
return DP_helper(isScramblePair, s1, s2);
}
};
``````

The recursive version has exponential complexity. To further improve the performance, we can use bottom-up DP, which is O(N^4) complexity. Here we build a table isS[len][i][j], which indicates whether s1[i..i+len-1] is a scramble of s2[j..j+len-1].

``````class Solution {
public:
bool isScramble(string s1, string s2) {
int sSize = s1.size(), len, i, j, k;
if(0==sSize) return true;
if(1==sSize) return s1==s2;
bool isS[sSize+1][sSize][sSize];

for(i=0; i<sSize; ++i)
for(j=0; j<sSize; ++j)
isS[1][i][j] = s1[i] == s2[j];

for(len=2; len <=sSize; ++len)
for(i=0; i<=sSize-len; ++i)
for(j=0; j<=sSize-len; ++j)
{
isS[len][i][j] = false;
for(k=1; k<len && !isS[len][i][j]; ++k)
{
isS[len][i][j] = isS[len][i][j] || (isS[k][i][j] && isS[len-k][i+k][j+k]);
isS[len][i][j] = isS[len][i][j] || (isS[k][i+len-k][j] && isS[len-k][i][j+k]);
}
}
return isS[sSize][0][0];

}
};
``````

Furhtermore, in many cases, we found we can terminate our recursion early by pruning: i.e. by first checking if s1 and s2 have the same character set before we do recursion: if not, just terminate without recursion. This observation leads us to the following Recursion+cache+pruning version. Here the key of the cache changes to idx1sSize +idx2 + lensSize*sSize;

``````class Solution {
private:
bool DP_helper(string &s1, string &s2, int idx1, int idx2, int len, char isS[])
{
int sSize = s1.size(),i, j, k, hist[26] , zero_count =0;
if(isS[(len*sSize+idx1)*sSize+idx2]) return isS[(len*sSize+idx1)*sSize+idx2]==1;
bool res = false;

fill_n(hist, 26, 0);
for(k=0; k<len;++k)
{ // check if s1[idx1:idx1+len-1] and s2[idx2:idx2+len-1] have same characters
zero_count +=  (0==hist[s1[idx1+k]-'a']) - (0== ++hist[s1[idx1+k]-'a']);
zero_count +=  (0==hist[s2[idx2+k]-'a']) - (0== --hist[s2[idx2+k]-'a']);
}
if(zero_count) {isS[(len*sSize+idx1)*sSize+idx2] = 2; return false;} //if not, return directly
if(len==1)     {isS[(len*sSize+idx1)*sSize+idx2] = 1; return true;}
for(k=1;k<len && !res;++k) //otherwise, recursion with cache
{
res = res || (DP_helper(s1, s2, idx1, idx2, k, isS) && DP_helper(s1, s2, idx1+k, idx2+k, len-k, isS) );
res = res || (DP_helper(s1, s2, idx1+len-k, idx2, k, isS) && DP_helper(s1, s2, idx1, idx2+k, len-k, isS) );
}
isS[(len*sSize+idx1)*sSize+idx2] = res?1:2;
return res;
}
public:
bool isScramble(string s1, string s2) {
const int sSize = s1.size();
if(0==sSize) return true;
char isS[(sSize+1)*sSize*sSize];
fill_n(isS, (sSize+1)*sSize*sSize, 0);
return DP_helper(s1, s2, 0, 0, sSize, isS);
}
};``````

• This post is deleted!

• genius idea and very nice explanation. However, I think the pruning is not helping here because it takes O(n) as the inner loop of method 2

``for(k=1; k<len && !isS[len][i][j]; ++k)``

• Why do we need to check this condition s2[len-k, len-1] and s2[0..len-k-1]?

• does this `bool isS[sSize+1][sSize][sSize];` work? sSize is not a constant..

• I think it works for some compiler. But certainly not all.

• Thanks for the nice and detailed explanation. I've been trying to do the pruning on a bottom-up DP version but couldn't get 4ms runtime, which makes me wondering the complexity of recursive memoization may be better than O(n^4).

Anyone tried to do pruning or any other optimizations with building DP matrix from bottom up and get less than 20ms?

• In fact,recursion with cache exactly has the same time complexity as bottom-up DP ，cause each subproblem would be solved only once and cached .No more exponential comlexity needed because there would be no more redundant work .You could use aggregation analysis for a more precise complexity results.However,as for some overhead in unordered_map cache operation,one would not be surprised to see a running time rise!

• @chenzhanhong Actually, based on the solution in OP, one could simply come up with the bottom up version without any usage of unordered_map but just arrays.

``````
class Solution {
public:
bool isScramble(string s1, string s2) {
if(s1.size()!=s2.size()) return false;
bool dp[s1.size()][s1.size()][s1.size()];
memset(dp, 0, s1.size()*s1.size()*s1.size());

for(int l=1; l<=s1.size(); l++){
for(int i=0; i+l<=s1.size(); i++){
for(int j=0; j+l<=s1.size(); j++){
if(l==1) dp[i][j][0] = s1[i]==s2[j];
else{
int cnt[26] = {0};
int zeros= 0;
for(int p =0; p<l; p++) {
zeros+=(cnt[s1[i+p]-'a']==0)-(++cnt[s1[i+p]-'a']==0);
zeros+=(cnt[s2[j+p]-'a']==0)-(--cnt[s2[j+p]-'a']==0);
}
if(zeros) {dp[i][j][l-1]=false;continue;}
for(int p = i+1; p-i<l; p++){
if(dp[i][j][l-1]) break;
dp[i][j][l-1] = (dp[i][j][p-i-1]&&dp[p][j+p-i][l-(p-i)-1])||(dp[i][j+l-(p-i)][p-i-1]&&dp[p][j][l-(p-i)-1]);
}
}
}
}
}
return dp[0][0][s1.size()-1];

}
};
``````

yet above solution takes 48ms to pass all tests. so that makes me wondering what I am missing here. Anyone has a clue?

• @dong.wang.1694
nice solution. But Could you explain why the recursive one is exponential? I think it's same with DP.

• @ltl58829
The 1st Recursive one divide s1,s2 with i, so basically it divides two strings into 4 parts, for each part we need to do (n/4) time search. So it's an O(4^N) exponential time algorithm.

• ``````  for(k=1; k<len && !isS[len][i][j]; ++k)
{
isS[len][i][j] = isS[len][i][j] || (isS[k][i][j] && isS[len-k][i+k][j+k]);
isS[len][i][j] = isS[len][i][j] || (isS[k][i+len-k][j] && isS[len-k][i][j+k]);
}
``````

Since isS[len][i][j] is always false. I think we don't need to include it into OR operation. Just simply

``````        isS[len][i][j] = (isS[k][i][j] && isS[len-k][i+k][j+k]) ||
(isS[k][i+len-k][j] && isS[len-k][i][j+k]);
``````

• The basic idea is to divide s1(s2) into two substrings with length k and len-k and check if the two substrings s1[0..k-1] and s1[k, len-1] are the scrambles of s2[0..k-1] and s2[k,len-1] or s2[len-k, len-1] and s2[0..len-k-1] via recursion. The straigtforward recursion will be very slow due to many repeated recursive function calls. To speed up the recursion, we can use an unordered_map isScramblePair to save intermediate results. The key used here is s1+s2, but other keys are also possible (e.g. using indices)

``````    class Solution {
bool DP_helper(unordered_map<string, bool> &isScramblePair, string s1, string s2)
{
int i,len = s1.size();
bool res = false;
if(0==len) return true;
else if(1==len) return s1 == s2;
else
{
if(isScramblePair.count(s1+s2)) return isScramblePair[s1+s2]; // checked before, return intermediate result directly
if(s1==s2) res=true;
else{
for(i=1; i<len && !res; ++i)
{
//check s1[0..i-1] with s2[0..i-1] and s1[i..len-1] and s2[i..len-1]
res = res || (DP_helper(isScramblePair, s1.substr(0,i), s2.substr(0,i)) && DP_helper(isScramblePair, s1.substr(i,len-i), s2.substr(i,len-i)));
//if no match, then check s1[0..i-1] with s2[len-k.. len-1] and s1[i..len-1] and s2[0..len-i]
res = res || (DP_helper(isScramblePair, s1.substr(0,i), s2.substr(len-i,i)) && DP_helper(isScramblePair, s1.substr(i,len-i), s2.substr(0,len-i)));
}
}
return isScramblePair[s1+s2]= res; //save the intermediate results

}
}
public:
bool isScramble(string s1, string s2) {
unordered_map<string, bool> isScramblePair;
return DP_helper(isScramblePair, s1, s2);
}
};
``````

The recursive version has exponential complexity. To further improve the performance, we can use bottom-up DP, which is O(N^4) complexity. Here we build a table isS[len][i][j], which indicates whether s1[i..i+len-1] is a scramble of s2[j..j+len-1].

``````class Solution {
public:
bool isScramble(string s1, string s2) {
int sSize = s1.size(), len, i, j, k;
if(0==sSize) return true;
if(1==sSize) return s1==s2;
bool isS[sSize+1][sSize][sSize];

for(i=0; i<sSize; ++i)
for(j=0; j<sSize; ++j)
isS[1][i][j] = s1[i] == s2[j];

for(len=2; len <=sSize; ++len)
for(i=0; i<=sSize-len; ++i)
for(j=0; j<=sSize-len; ++j)
{
isS[len][i][j] = false;
for(k=1; k<len && !isS[len][i][j]; ++k)
{
isS[len][i][j] = isS[len][i][j] || (isS[k][i][j] && isS[len-k][i+k][j+k]);
isS[len][i][j] = isS[len][i][j] || (isS[k][i+len-k][j] && isS[len-k][i][j+k]);
}
}
return isS[sSize][0][0];

}
};
``````

Furhtermore, in many cases, we found we can terminate our recursion early by pruning: i.e. by first checking if s1 and s2 have the same character set before we do recursion: if not, just terminate without recursion. This observation leads us to the following Recursion+cache+pruning version. Here the key of the cache changes to idx1sSize +idx2 + lensSize*sSize;

``````class Solution {
private:
bool DP_helper(string &s1, string &s2, int idx1, int idx2, int len, char isS[])
{
int sSize = s1.size(),i, j, k, hist[26] , zero_count =0;
if(isS[(len*sSize+idx1)*sSize+idx2]) return isS[(len*sSize+idx1)*sSize+idx2]==1;
bool res = false;

fill_n(hist, 26, 0);
for(k=0; k<len;++k)
{ // check if s1[idx1:idx1+len-1] and s2[idx2:idx2+len-1] have same characters
zero_count +=  (0==hist[s1[idx1+k]-'a']) - (0== ++hist[s1[idx1+k]-'a']);
zero_count +=  (0==hist[s2[idx2+k]-'a']) - (0== --hist[s2[idx2+k]-'a']);
}
if(zero_count) {isS[(len*sSize+idx1)*sSize+idx2] = 2; return false;} //if not, return directly
if(len==1)     {isS[(len*sSize+idx1)*sSize+idx2] = 1; return true;}
for(k=1;k<len && !res;++k) //otherwise, recursion with cache
{
res = res || (DP_helper(s1, s2, idx1, idx2, k, isS) && DP_helper(s1, s2, idx1+k, idx2+k, len-k, isS) );
res = res || (DP_helper(s1, s2, idx1+len-k, idx2, k, isS) && DP_helper(s1, s2, idx1, idx2+k, len-k, isS) );
}
isS[(len*sSize+idx1)*sSize+idx2] = res?1:2;
return res;
}
public:
bool isScramble(string s1, string s2) {
const int sSize = s1.size();
if(0==sSize) return true;
char isS[(sSize+1)*sSize*sSize];
fill_n(isS, (sSize+1)*sSize*sSize, 0);
return DP_helper(s1, s2, 0, 0, sSize, isS);
}
};
``````

The recursive version has exponential complexity. To further improve the performance, we can use bottom-up DP, which is O(N^4) complexity.

why dos it say that recursion with memoization (top-down DP) has exponential complexity? Isn't its complexity same as bottom-up DP which is N^4 ?

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