package leetcode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * https://leetcode.com/problems/scramble-string/
 */
public class Problem87 {
    public boolean isScramble(String s1, String s2) {
        Set<String> set = scramble(s1, new HashMap<>());
        return set.contains(s2);
    }

    private static Set<String> scramble(String str, Map<String, Set<String>> memo) {
        if (memo.containsKey(str)) {
            return memo.get(str);
        }
        if (str.isEmpty()) {
            return new HashSet<>();
        }
        if (str.length() == 1) {
            Set<String> set = new HashSet<>();
            set.add(str);
            return set;
        }
        Set<String> set = new HashSet<>();
        for (int i = 1; i < str.length(); i++) {
            String sub1 = str.substring(0, i);
            String sub2 = str.substring(i);
            Set<String> set1 = scramble(sub1, memo);
            Set<String> set2 = scramble(sub2, memo);
            for (String s1 : set1) {
                for (String s2 : set2) {
                    set.add(s1 + s2);
                }
            }
            for (String s2 : set2) {
                for (String s1 : set1) {
                    set.add(s2 + s1);
                }
            }
        }
        memo.put(str, set);
        return set;
    }

    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
        System.out.println(prob.isScramble("abcdefghij", "efghijcadb")); // false
    }
}

@@ -1005,32 +1005,81 @@
 le(sub2, memo);%0A
+            if (set1.size() %3E set2.size()) %7B%0A    
             for 
@@ -1107,32 +1107,36 @@
                 
+  
+  
 for (String s2 :
@@ -1156,32 +1156,36 @@
                 
+    
 set.add(s1 + s2)
@@ -1182,24 +1182,88 @@
 d(s1 + s2);%0A
+                        set.add(s2 + s1);%0A                    %7D%0A
             
@@ -1273,32 +1273,39 @@
  %7D%0A            %7D
+ else %7B
 %0A            for
@@ -1293,32 +1293,36 @@
 e %7B%0A            
+    
 for (String s2 :
@@ -1322,32 +1322,36 @@
 ng s2 : set2) %7B%0A
+    
                 
@@ -1395,33 +1395,101 @@
         
-set.add(s2 + s1);
+    set.add(s1 + s2);%0A                        set.add(s2 + s1);%0A                    %7D
 %0A       

Update problem 87