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);
            if (set1.size() > set2.size()) {
                for (String s1 : set1) {
                    for (String s2 : set2) {
                        set.add(s1 + s2);
                        set.add(s2 + s1);
                    }
                }
            } else {
                for (String s2 : set2) {
                    for (String s1 : set1) {
                        set.add(s1 + s2);
                        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
    }
}

@@ -284,16 +284,20 @@
 mble(s1,
+ s2,
  new Has
@@ -397,16 +397,30 @@
 ring str
+1, String str2
 , Map%3CSt
@@ -478,16 +478,17 @@
 sKey(str
+1
 )) %7B%0A   
@@ -511,24 +511,25 @@
 memo.get(str
+1
 );%0A        %7D
@@ -544,16 +544,17 @@
  if (str
+1
 .isEmpty
@@ -620,16 +620,17 @@
  if (str
+1
 .length(
@@ -709,16 +709,17 @@
 .add(str
+1
 );%0A     
@@ -821,16 +821,17 @@
  i %3C str
+1
 .length(
@@ -865,24 +865,25 @@
 g sub1 = str
+1
 .substring(0
@@ -917,16 +917,17 @@
 b2 = str
+1
 .substri
@@ -978,16 +978,22 @@
 le(sub1,
+ str2,
  memo);%0A
@@ -1037,16 +1037,22 @@
 le(sub2,
+ str2,
  memo);%0A
@@ -1206,34 +1206,176 @@
         
-set.add(s1 + s2);%0A
+if (str2.contains(s1 + s2)) %7B%0A                            set.add(s1 + s2);%0A                        %7D%0A                        if (str2.contains(s2 + s1)) %7B%0A    
         
@@ -1420,34 +1420,42 @@
                 
+   
+ 
 %7D%0A
+    
                 
@@ -1448,32 +1448,50 @@
               %7D%0A
+                %7D%0A
             %7D el
@@ -1597,39 +1597,49 @@
                 
-set.add
+if (str2.contains
 (s1 + s2);%0A     
@@ -1623,34 +1623,40 @@
 ontains(s1 + s2)
-;%0A
+) %7B%0A    
                 
@@ -1664,38 +1664,38 @@
        set.add(s
-2
+1
  + s
-1
+2
 );%0A             
@@ -1693,32 +1693,36 @@
                 
+  
+  
 %7D%0A              
@@ -1719,34 +1719,32 @@
             
-%7D%0A
         
     %7D%0A      
@@ -1735,528 +1735,222 @@
     
-    %7D%0A        %7D%0A        memo.put(str, set);%0A        return set;%0A
+if (str2.contains(s2 + s1)) %7B%0A                            set.add(s2 + s1);%0A                  
     
+  
 %7D
-%0A
 %0A    
-public static void main(String%5B%5D args) %7B%0A        Problem87 prob = new Problem87();%0A        System.out.println(prob.isScramble(%22great%22, %22rgeat%22)); // true%0A        System.out.println(prob.isScramble(%22great%22, %22rgtae%22)); // true%0A
+                %7D%0A                %7D%0A         
    
+%7D%0A
      
-System.out.println(prob.isScramble(%22abcd%22, %22bdac%22)); // false%0A        System.out.println(prob.isScramble(%22abcd%22, %22acdb%22)); // true%0A        System.out.println(prob.isScramble(%22abcdefghij%22, %22efghijcadb%22)); // false
+   %7D%0A        memo.put(str1, set);%0A        return set;
 %0A   

Solve problem 87