package leetcode;

/**
 * https://leetcode.com/problems/scramble-string/
 */
public class Problem87 {
    public boolean isScramble(String s1, String s2) {
        // TODO
        return false;
    }

    public static void main(String[] args) {
        Problem87 prob = new Problem87();
        System.out.println(prob.isScramble("great", "rgeat")); // true
        System.out.println(prob.isScramble("great", "rgtae")); // true
        System.out.println(prob.isScramble("abcd", "bdac")); // false
        System.out.println(prob.isScramble("abcd", "acdb")); // true
    }
}

@@ -12,16 +12,113 @@
 tcode;%0A%0A
+import java.util.HashMap;%0Aimport java.util.HashSet;%0Aimport java.util.Map;%0Aimport java.util.Set;%0A%0A
 /**%0A * h
@@ -258,36 +258,1119 @@
     
-// TODO%0A        return false
+Set%3CString%3E set = scramble(s1, new HashMap%3C%3E());%0A        return set.contains(s2);%0A    %7D%0A%0A    private static Set%3CString%3E scramble(String str, Map%3CString, Set%3CString%3E%3E memo) %7B%0A        if (memo.containsKey(str)) %7B%0A            return memo.get(str);%0A        %7D%0A        if (str.isEmpty()) %7B%0A            return new HashSet%3C%3E();%0A        %7D%0A        if (str.length() == 1) %7B%0A            Set%3CString%3E set = new HashSet%3C%3E();%0A            set.add(str);%0A            return set;%0A        %7D%0A        Set%3CString%3E set = new HashSet%3C%3E();%0A        for (int i = 1; i %3C str.length(); i++) %7B%0A            String sub1 = str.substring(0, i);%0A            String sub2 = str.substring(i);%0A            Set%3CString%3E set1 = scramble(sub1, memo);%0A            Set%3CString%3E set2 = scramble(sub2, memo);%0A            for (String s1 : set1) %7B%0A                for (String s2 : set2) %7B%0A                    set.add(s1 + s2);%0A                %7D%0A            %7D%0A            for (String s2 : set2) %7B%0A                for (String s1 : set1) %7B%0A                    set.add(s2 + s1);%0A                %7D%0A            %7D%0A        %7D%0A        memo.put(str, set);%0A        return set
 ;%0A  
@@ -1673,16 +1673,16 @@
 / false%0A
-
         
@@ -1738,20 +1738,102 @@
 )); // true%0A
+        System.out.println(prob.isScramble(%22abcdefghij%22, %22efghijcadb%22)); // false%0A
     %7D%0A%7D%0A

Update problem 87