Brace Expansion

This medium LC problem asks us to return all the words formed by expanding the characters inside the braces and appending it to all the other characters present in the string.

This can be solved by standard DFS approach.

class Solution {
    public String[] expand(String S) {
        List<String> collector = new ArrayList<>();
        
        helper(0, S, "", collector);
        Collections.sort(collector);
        
        return collector.toArray(new String[0]);
    }
    
    private void helper(int index, String input, String current, List<String> collector) {
        if(index == input.length()){
            collector.add(current);
            return;
        }
        
        char inputChar = input.charAt(index);
        
        if(inputChar == '{') {
            // start collecting chars
            index++;
            List<Character> cList = new ArrayList<>();
            while(index < input.length() && input.charAt(index) != '}'){
                if(Character.isLetter(input.charAt(index))){
                    cList.add(input.charAt(index));    
                }
                index++;                
            }
            
            index++;
            
            // then recursively call helper function
            // by appending each character to the current string
            for(Character c : cList){
                helper(index, input, current + c, collector);
            }
        }else {
            // if the current character isn't a start of braces and it's just 
            // a letter, just append it to the current string.
            helper(index + 1, input, current + inputChar, collector);
        }
    }
}
Runtime: 7 ms, faster than 23.58% of Java online submissions for Brace Expansion.
Memory Usage: 41.5 MB, less than 50.00% of Java online submissions for Brace Expansion.
comments powered by Disqus