Optimized recursive (0ms) and DP (20ms) solution C beating 100% submissions


  • 12

    Simply we can just use recursive method to traverse every possible situations but as we can expect that we will run into TLE.

    There are other factors we should make full use of to reduce the traversing range

    • the limited characters
    • the scrambled string is containing just exactly the same set of characters as the original string

    which can be used to prune almost all invalid traversing branches and result in the best time cost.

    #define SIZE 256
    bool isnScramble(char* s1, char* s2, int len) 
    {
        
        if(!strncmp(s1, s2, len)) return true;
        int count[SIZE] = {0};
        for(int i = 0; i < len; i++)
            count[s1[i]-'a']++, count[s2[i]-'a']--;
        for(int i = 0; i < SIZE; i++)
            if(count[i]) return false;
        for(int i=1; i < len; i++)
            if(isnScramble(s1, s2, i) && isnScramble(s1+i, s2+i, len-i) ||
                    isnScramble(s1, s2+len-i, i) && isnScramble(s1+i, s2, len-i)) return true;
        return false;
    }
    
    //AC - 0ms - beats 100% submissions;
    bool isScramble(char* s1, char* s2)
    {
        int len = strlen(s1);
        return isnScramble(s1, s2, len);
    }
    

    A DP solution is also provided here with 20ms time cost, which is inspired by the above recursive method using three-dimension array to store the state

    match[size][index1][index2]

    the size is the comparing size of the two strings, index1 is the start index of string 1 and index2 is that of string 2.

    //AC - 20ms - beats 100% submissions - DP solution;
    bool isScramble(char* s1, char* s2)
    {
        int len = strlen(s1);
        if(!len) return true;
        if(len==1) return *s1==*s2;
        bool*** match = (bool***)malloc(sizeof(bool**)*(len+1));
        for(int i = 0; i <= len; i++)
        {
            match[i] = (bool**)malloc(sizeof(bool*)*len);
            for(int j = 0; j < len; j++)
            {
                match[i][j] = (bool*)malloc(sizeof(bool)*len);
                memset(match[i][j], 0, sizeof(bool)*len);
            }
        }
        for(int i = 0; i < len; i++)
            for(int j = 0; j < len; j++)
                match[1][i][j] = (s1[i] == s2[j]);
        for(int size = 2; size <= len; size++)
            for(int i = 0; i <= len-size; i++)
                for(int j = 0; j <= len-size; j++)
                    for(int k = 1; k<size && !match[size][i][j]; k++)
                        match[size][i][j] = (match[k][i][j] && match[size-k][i+k][j+k]) || (match[k][i+size-k][j] && match[size-k][i][j+k]);
        return match[len][0][0];
    }
    

    There are still lots of redundant search in the above methods; can someone further improve it? Thanks in advance!


  • 0

    Why not using memoization in the first recursive solution?


  • 0

    Another question, why do you initialize match to be a bool*** of size len + 1 and not len?


  • 0

    the state is too complicated here, we cannot simply use memorization to pruning the branches. As for your second question, you should read the explanation again, the size is the length of the string, so we have to allocate len+1 so match its range can be [0...len]. Good luck!


  • 0
    S

    @LHearen Impressive


  • 1

    Related C++ solutions:

    class Solution {
    public:
        bool isnScramble(char* s1, char* s2, int len) {
        if(!strncmp(s1, s2, len)) return true;
        int count[26] = {0};
        for(int i = 0; i < len; i++) count[s1[i]-'a']++, count[s2[i]-'a']--;
        for(int i = 0; i < 26; i++) if(count[i]) return false;
        for(int i=1; i < len; i++)
            if((isnScramble(s1, s2, i) && isnScramble(s1+i, s2+i, len-i)) ||
                    (isnScramble(s1, s2+len-i, i) && isnScramble(s1+i, s2, len-i))) return true;
        return false;
        }
        bool isScramble(string s1, string s2) {
            return isnScramble((char*)s1.c_str(), (char*)s2.c_str(), s1.length());
        }
    };
    

    DP in C++

    class Solution {
    public:
    bool isScramble(string s1, string s2){
        int len = s1.length();
        if(!len) return true;
        if(len==1) return s1==s2;
        vector<vector<vector<bool>>> match(len+1, vector<vector<bool>>(len, vector<bool>(len, false)));
        for(int i = 0; i < len; i++)
            for(int j = 0; j < len; j++)
                match[1][i][j] = (s1[i] == s2[j]);
        for(int d = 2; d <= len; d++)
            for(int i = 0; i <= len-d; i++)
                for(int j = 0; j <= len-d; j++)
                    for(int k = 1; k<d && !match[d][i][j]; k++)
                        match[d][i][j] = (match[k][i][j] && match[d-k][i+k][j+k]) || (match[k][i+d-k][j] && match[d-k][i][j+k]);
        return match[len][0][0];
      }
    };

  • 1
    M

    The recursive solution illustrated at the top helped, it does clarify the whole approach.

    Main hurdle to understanding such problems would be identifying that relevant repeating sub structure we need to operate on. As always, there is a repeating pattern here.

    Consider a trivial use case where string1 = "me" and string2 = "em". We need to identify whether "em" is a scrambled version of "me". Here the length is 2 and there is only one possible way we can scramble "me". Basically by switching the children.

    alt text

    Longer strings would constitute of numerous such sub-trees. For each sub-structure (or sub-tree) we need to compare with corresponding sub-tree in string2, before and after switching the children.

    A method where we recursively parse each of these sub-trees would seem ideal. That would also mean that we can have a hit only when all the sub-trees of the scrambled string1 matches with the sub-trees of string2.

    Also, strings with more than 2 characters can have more than one binary tree representation. So we also need a loop to sequentially split the string at various locations.

    Recursive DFS approach with memorization is given below!

    int rscr(char *s1, char *s2, int slen, int len, int s1off, int s2off,
             char *dp)
    {
        int i, dpoff = (s1off * slen * slen + s2off * slen + len - 1);
    
        /* If the result is cached, then return the same */
        if (dp[dpoff] != 2)
            return dp[dpoff];
    
        /* If it's the leaf node */
        if (len == 1)
            return dp[dpoff] = (s1[s1off] == s2[s2off]) ? TRUE : FALSE;
    
        /* Ensure the strings consist of same characters */
        if (!gen_map(&s1[s1off], &s2[s2off], len))
            return dp[dpoff] = FALSE;
    
        /* Generate different binary trees by splitting the string
           at various locations. First check without switching the left &
           right children, then with the switch */
        for (i = 1 ; i < len; ++i)
            if ((rscr(s1, s2, slen, len - i, s1off + i, s2off + i, dp) &&
                 rscr(s1, s2, slen, i, s1off, s2off, dp)) || // no swap
                (rscr(s1, s2, slen, len - i, s1off + i, s2off, dp) &&
                 rscr(s1, s2, slen, i, s1off, s2off + len - i, dp))) // swap
                return dp[dpoff] = TRUE;
    
        /* Fail */
        return FALSE;
    }
    

    Bit bucket link for the full source.


  • 0
    W

    int count[26] = {0};
    for(int i = 0; i < len; i++)
    count[s1[i]-'a']++, count[s2[i]-'a']--;

    why count[26] ? 26 maybe make the array out of bounds! pls.


  • 0

    @weeyanghuang It's clearly pointed out by the problem statements that there are only lowercase letters (which is now removed), so here we should expand the 26 to 256 to blend into the new situation. Thanks for your feedback!


Log in to reply
 

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