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


  • 56
    D

    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);
        }
    };

  • -2
    G
    This post is deleted!

  • 0
    K

    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)

  • 0
    B

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


  • 0
    A

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


  • 0
    Y

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


  • 0
    F

    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?


  • 3
    C

    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!


  • 0
    F

    @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?


  • 0
    L

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


  • 0

    @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.


  • 0

    @dong.wang.1694 said in My C++ solutions (recursion with cache , DP, recursion with cache and pruning) with explanation (4ms):

      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]);
    

    Some comments would be helpful for understanding.


Log in to reply
 

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