Share my 4ms c++ recursive solution


  • 99
    R

    Assume the strings are all lower case letters

    class Solution {
    public:
        bool isScramble(string s1, string s2) {
            if(s1==s2)
                return true;
                
            int len = s1.length();
            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]!=0)
                    return false;
            }
            
            for(int i=1; i<=len-1; i++)
            {
                if( isScramble(s1.substr(0,i), s2.substr(0,i)) && isScramble(s1.substr(i), s2.substr(i)))
                    return true;
                if( isScramble(s1.substr(0,i), s2.substr(len-i)) && isScramble(s1.substr(i), s2.substr(0,len-i)))
                    return true;
            }
            return false;
        }
    };

  • 0

    Easy and clear idea! The code is also very fast. But would you turn the recursive part into DP?


  • 0
    F

    I'm afraid that idea won't work. This code runs fast because it uses an very efficient pruning (count alphabat), but you can't use pruning within DP


  • 0
    M

    And you might depend on all characters in s1 and s2 are lowercase


  • 1
    L

    Turning the type of "count" to unordered_map<char, int> could handle any chars.


  • 10
    K

    you don't have to assume only low case letters if you use an array of 256

        public boolean isScramble(String s1, String s2) {
        int len1 = s1.length(), len2 = s2.length();
        if (len1 != len2) return false;
        if (len1 == 0) return true;
        // pruning 
        if (s1.equals(s2)) return true;
        int[] count = new int[256];
        for (int i = 0; i < len1; i++){
            count[s1.charAt(i)]++;
            count[s2.charAt(i)]--;
        }
        for (int i = 0; i < len1; i++){
            if (count[s1.charAt(i)] != 0) return false;
        }
        for (int i = 1; i < len1; i++){
            if (isScramble(s1.substring(0, i), s2.substring(0, i)) && isScramble(s1.substring(i), s2.substring(i)))
                return true;
            if (isScramble(s1.substring(0, i), s2.substring(len1 - i)) && isScramble(s1.substring(i), s2.substring(0, len1 - i)))
                return true;
        }
        return false;
    }

  • 0
    M

    You are right~many thanks~


  • 0
    S
    This post is deleted!

  • 11
    A

    "bcdebcdebcdebcdebcdebcdebcdebcdebcdebcdebcdebcdebcdebcdebcdebcdebcdebcdebcdebcdebcdebcde"
    "cebdcebdcebdcebdcebdcebdcebdcebdcebdcebdcebdcebdcebdcebdcebdcebdcebdcebdcebdcebdcebdcebd"

    Given this test case, your method will TLE.


  • 1
    W
       Good solution with pruning! My code but use an unordered_map. 
    
    class Solution {
        public:
            bool isScramble(string s1, string s2) {
            if(s1==s2) return true;
            unordered_map<char,int> strmap;
            int length=s1.size();
            for(int i=0;i<length;i++)
            {
                strmap[s1[i]]++;
                strmap[s2[i]]--;
            }
            for(int i=0;i<length;i++)
            {
                if(strmap[s1[i]]!=0 )
                return false;
            }
            for(int i=1;i<length;i++)
            {
                if(isScramble(s1.substr(0,i),s2.substr(0,i)) && isScramble( s1.substr(i),s2.substr(i) )  )
                return true;
                if(isScramble( s1.substr(0,i),s2.substr(length-i) ) && isScramble( s1.substr(i),s2.substr(0,length-i) )  )
                return true;
            }
            return false;
            }
        };

  • 0
    W

    NA, please ignore my comments.


  • 0
    G

    what is time complexity in the worse case? O(2^n)?

    Given complexity f(i-1) and no pruning occurs

    f(i) = 2f(i-1) + something(f(i-2) ??


  • 0
    B

    why the code runs even faster than DP?


  • 3
    F

    @XiaoboZhang1991

    Computation costs money, it should be done in less than 1s. So the test cases are very limited.

    Try the test case supplied by athenalin.shi on your own machine. dp will return in a few ms, and this recursive alg. will hopefully return in hours.

    Quite a few people here said recursion (without cache) is better than dp, and gave a reason that recursion has something called "pruning". Pruning means nothing when the two strings mismatch.

    BTW, recursive (without cache) is O(a^n), dp is O(n^a)


  • 0

    why dp runs 176ms..


  • 0
    B

    @mwx36mwx
    Actually, dp visits more status than recursive with pruning and memorized does.


  • 0
    S

    @Bigbear1991 Test cases are weak. The code will TLE on
    "bcdebcdebcdebcdebcdebcdebcdebcdebcdebcdebcdebcdebcdebcdebcdebcdebcdebcdebcdebcdebcdebcde"
    "cebdcebdcebdcebdcebdcebdcebdcebdcebdcebdcebdcebdcebdcebdcebdcebdcebdcebdcebdcebdcebdcebd"


  • 0
    H
    bool isScramble(string s1, string s2) {
            if(s1 == s2) return true;
            
            int n = s1.length();
            int count [26] = {0};
            
            for(int i = 0; i < n; i++) {count[s1[i]-'a']++; count[s2[i]-'a']--;}
            for(int i = 0; i < 26; i++) if(count[i] != 0) return false;
            
            for(int i = 1; i < n; i++){
                if(isScramble(s1.substr(0, i), s2.substr(0, i)) && isScramble(s1.substr(i), s2.substr(i))) return true;
                if(isScramble(s1.substr(0, i), s2.substr(n-i)) && isScramble(s1.substr(i), s2.substr(0, n-i))) return true;
            }
            
            return false;
        }

  • 0
    L
    This post is deleted!

  • 0
    R

    Can someone explain the recursion part of the code, Thank you.


Log in to reply
 

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