7ms AC simple Java no DP, no sort, no count, no hashtable, with a speed up trick


  • 2
    C

    The trick is to do the shorter sub string first, hoping it fails quickly and avoid doing the longer one.

    boolean isit(char[] s1, char[] s2, int b1, int e1, int b2, int e2) {
        int len = e1-b1;
        if (1 == len) return s1[b1] == s2[b2];
        for (int n = 1; n <= len/2; ++n) {
            if (isit(s1, s2, b1, b1+n, b2, b2+n) && isit(s1, s2, b1+n, e1, b2+n, e2)) return true;
            if (isit(s1, s2, b1, b1+n, e2-n, e2) && isit(s1, s2, b1+n, e1, b2, e2-n)) return true;
            if (n == len-n) continue;
            if (isit(s1, s2, e1-n, e1, b2, b2+n) && isit(s1, s2, b1, e1-n, b2+n, e2)) return true;
            if (isit(s1, s2, e1-n, e1, e2-n, e2) && isit(s1, s2, b1, e1-n, b2, e2-n)) return true;
        }
        return false;
    }
    public boolean isScramble(String s1, String s2) {
        return isit(s1.toCharArray(), s2.toCharArray(), 0, s1.length(), 0, s2.length());
    }

  • 0
    R

    Can you help to clarify the complexity please? Thank you!


  • 0
    C

    Sorry I can't. Seems a bit too complicated. Any one can help here?


Log in to reply
 

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