JAVA 2ms nlogn recursive solution


  • 2
    I

    There are on average logn levels of recursive call, at each level, all together all chars are visit linearly.

    public boolean isScramble(String s1, String s2) {
        int n = s1.length();
        if (n == 1) return s1.equals(s2);
        int[] map1 = new int[128], map2 = new int[128];
        for (int i = 0, cnt1 = 0, cnt2 = 0; i < n-1; i++) {
            if (map1[s1.charAt(i)]++ < 0) cnt1++;
            if (map1[s2.charAt(i)]-- > 0) cnt1++;
            if (cnt1 == i+1 &&
                isScramble(s1.substring(0, cnt1), s2.substring(0, cnt1)) && 
                isScramble(s1.substring(cnt1), s2.substring(cnt1))) return true;
            if (map2[s1.charAt(i)]++ < 0) cnt2++;
            if (map2[s2.charAt(n-1-i)]-- > 0) cnt2++;
            if (cnt2 == i+1 &&
                isScramble(s1.substring(0, cnt2), s2.substring(n-cnt2)) &&
                isScramble(s1.substring(cnt2), s2.substring(0, n-cnt2))) return true;
        }
        return false;
    }
    

    }


  • 0
    G

    can u add a little bit comments?


  • 0
    I

    Scan s1 and s2 in order, if found first cnt chars set are the same in s1 and s2, recursive call.
    Scan s1 in order s2 reversely, if found first cnt chars set are the same, recursive call.
    If s1 and s2 have length of 1, return if there are equal.


Log in to reply
 

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