Sharing my 16ms C++ solution


  • 0
    T
    class Solution {
    private:
        bool isScrambleHelper(char* s1, char* s2, int n)
        {
            if(n<=0)
                return true;
                
            int i;
            for(i=0; i<n; i++)
                if(s1[i]!=s2[i])
                    break;
                    
            if(i==n)
                return true;
                
            vector<int> count(256, 0);
            for(i=0; i<n; i++)
            {
                count[s1[i]]++;
                count[s2[i]]--;
            }
            for(i=0; i<256; i++)
                if(count[i]!=0)
                    return false;
                    
            for(int length=1; length<n; length++)
            {
                if(isScrambleHelper(s1, s2, length) && isScrambleHelper(s1+length, s2+length, n-length))
                    return true;
                if(isScrambleHelper(s1, s2+n-length, length) && isScrambleHelper(s1+length, s2, n-length))
                    return true;
            }
            
            return false;
        }
    public:
        bool isScramble(string s1, string s2) {
            int n = s1.length();
            char S1[n+1];
            char S2[n+1];
            strcpy(S1, s1.c_str());
            strcpy(S2, s2.c_str());
            return isScrambleHelper(S1, S2, n);
        }
    };

Log in to reply
 

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