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


  • 0
    S

    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>();
            scrambledStrings.add(s);
            map.put(s, scrambledStrings);
            return scrambledStrings;
        }
        if(s.length() == 2){
            Set<String> scrambledStrings = new HashSet<String>();
            scrambledStrings.add(s);
            scrambledStrings.add((new StringBuilder(s).reverse().toString()));
            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);
                    scrambledStrings.add(sb.append(subRight).toString());
                    sb.setLength(0);
                }
                sb.setLength(0);
            }
            
            for(String subLeft : scrambledStringsForLeft){
                for(String subRight : scrambledStringsForRight){
                    sb.append(subRight);
                    scrambledStrings.add(sb.append(subLeft).toString());
                    sb.setLength(0);
                }
                sb.setLength(0);
            }
        }
        map.put(s, scrambledStrings);
        return map.get(s);
    }

Log in to reply
 

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