Accepted Java solution


  • 75
    B
    public class Solution {
        public boolean isScramble(String s1, String s2) {
            if (s1.equals(s2)) return true; 
            
            int[] letters = new int[26];
            for (int i=0; i<s1.length(); i++) {
                letters[s1.charAt(i)-'a']++;
                letters[s2.charAt(i)-'a']--;
            }
            for (int i=0; i<26; i++) if (letters[i]!=0) return false;
        
            for (int i=1; i<s1.length(); 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(s2.length()-i)) 
                 && isScramble(s1.substring(i), s2.substring(0,s2.length()-i))) return true;
            }
            return false;
        }
    }

  • -1
    N

    For recursion method, what is the time complexity? is it O(n^3)?


  • -1
    W

    i think it's O(n^3)


  • 1
    Y

    This is exponential complexity, something like O(3^n).


  • 2
    S

    exponential complexity O(2^n)


  • 0
    R

    Can some one explain the logic of two if conditions, I got what it is doing, but can`t understand why this condition is sufficient to check scramble strings?

    Thanks in advance !!


  • 13
    P

    @ranhar The 1st IF is to check the LEFT child of S1 is scramble of LEFT child of S2 AND RIGHT child of S1 is also a scramble of RIGHT child of s2.
    When this fails, it means the left and right substrings are swapped.
    The 2nd IF statement check for the swap case with LEFT child of S1 and RIGHT child of S2 AND RIGHT child of S1 and LEFT child of S2.
    I hope this clear it up.


  • 5
    X

    Nice Solution, but I just add one line to make it better.
    directly check length(), if not same return false, we don't need to go through counting all the letters' numbers.

    Personally thinking this Time complexity should be O(4^n), because one problem are almost divided into 4 sub problem. Please correct me if I am wrong.

        public boolean isScramble(String s1, String s2) {
            if(s1 == null || s2 == null) return false;
            if(s1.equals(s2)) return true;
            if(s1.length()!=s2.length()) return false;
            
            int[] letters = new int[26];
            int len = s1.length();
            for(int i = 0; i < len; i++){
                letters[s1.charAt(i)-'a']++;
                letters[s2.charAt(i)-'a']--;
            }
            for(int i = 0; i < 26; i++){
                if(letters[i]!= 0) return false;
            }
            
            for(int i = 1; i < len; 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(len-i)) && isScramble(s1.substring(i), s2.substring(0,len-i))) return true;
            }
            return false;
        }
    }

  • 0
    R

    @paullightman Thanks a lot, it make sense now


  • 0
    This post is deleted!

  • 0
    R

    Golang version:

    func isScramble(s1 string, s2 string) bool {
        if s1 == s2 { return true}
        
            letters := make([]int, 26)
            for i:=0; i < len(letters); i++ {
                letters[i] = 0
            }
            for i:=0; i < len(s1); i++ {
                letters[int(s1[i])-int('a')]++
                letters[int(s2[i])-int('a')]--
            }
            for i:=0; i<26; i++ {
                if letters[i]!=0 {
                    return false
                }
            }
            for i:=1; i<len(s1); i++ {
                if isScramble(s1[0:i], s2[0:i]) && isScramble(s1[i:], s2[i:]) {
                     return true
                }
                if isScramble(s1[0:i], s2[len(s2)-i:]) && isScramble(s1[i:], s2[0:len(s2)-i]) {
                     return true
                }
            }
            return false
    }
    

  • 5
    M

    I think the time-complexity is O(n!),
    T(n) = nT(n-1) = n(n-1)*T(n-2), .... O(n!)
    please correct me if I'm wrong


  • 0

    Elegant solution!


  • 0
    R

    Sorry, I am asking a very naive question, why can't we just sort the strings and compare, if both are equal like anagram check, then these must be scrambled. Please clear my doubt.


  • 0
    N

    Great optimization!

    Is the time complexity O(2^n)? But according to LeetCode, it runs faster than the DP solution O(n ^ 4).

    Also, should we use 'int[] letters = new int[256]'; instead of 'int[] letters = new int[26];' since it doesn't mention the strings are lower case only?


  • 0
    F

    @zhangzhaoyu1985 I really got the same puzzle.. How can this algorithm be quicker than the O(n ^ 4) solution? I guess it may because of the test cases?


  • 1
    S

    @rocksvashi Think about the following two strings: "abta" and "tbaa", they're anagrams but not scrambles of each other


  • 0
    R

    @szyyn95 ah! Yeah I really missed that important part, my bad. Thank you.


  • 0
    M

    @FelixGEEK Because the test cases are too weak (not long enough), for example, when n<=10, 2^n is smaller than n^4


  • 0
    F

    @MichaelZZZ Alright.. That may be the only the reason..


Log in to reply
 

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