One possible follow-up or mutation: did anyone try to generate all possible scrambled strings for s1?

• I saw lots of good solutions in Disucss to are very clever to solve this particular problem, but just as a follow up, if the interviewer asks how to generate all possible scrambled strings for one given string, how would one do it?
I gave it a shot here, but the time cost is pretty huge, and I'm out of ideas on how to optimize it. Any input is greatly appreciated.

``````Map<String, Set<String>> map = new HashMap();

public boolean isScramble(String s1, String s2) {
Set<String> set = generateAllScrambles(s1);
return set.contains(s2);
}

private Set<String> generateAllScrambles(String s) {
if(map.containsKey(s)) return map.get(s);
if(s.length() == 1){
Set<String> scrambledStrings = new HashSet<String>();
map.put(s, scrambledStrings);
return scrambledStrings;
}
if(s.length() == 2){
Set<String> scrambledStrings = new HashSet<String>();
map.put(s, scrambledStrings);
return scrambledStrings;
}

Set<String> scrambledStrings = new HashSet<String>();
for(int i = 1; i < s.length(); i++){
String left = s.substring(0, i), right = s.substring(i);
Set<String> scrambledStringsForLeft = generateAllScrambles(left);
Set<String> scrambledStringsForRight = generateAllScrambles(right);

StringBuilder sb = new StringBuilder();
for(String subLeft : scrambledStringsForLeft){
for(String subRight : scrambledStringsForRight){
sb.append(subLeft);
sb.setLength(0);
}
sb.setLength(0);
}

for(String subLeft : scrambledStringsForLeft){
for(String subRight : scrambledStringsForRight){
sb.append(subRight);