import java.util.*;

/**
 * 1087. 花括号展开
 */

public class Expand {
    public String[] expand(String s) {

        List<List<Character>> temp = new ArrayList<>();
        decode(s, temp);
        List<String> resList = new ArrayList<>();
        backtrack(0, temp, new StringBuilder(),resList);
        String[] res = new String[resList.size()];
        for(int i=0; i<resList.size(); i++){
            res[i] = resList.get(i);
        }
        return res;
    }

    void decode(String s, List<List<Character>> temp){
        boolean left = false;
        Queue<Character> queue = new PriorityQueue<>(
                (a, b) -> {
                    return a-b;
                }
        );
        for(char c: s.toCharArray()){
            if(c == '{'){
                left = true;
            }else if(c == '}'){
                List<Character> t = new ArrayList<>();
                while (!queue.isEmpty()){
                    t.add(queue.poll());
                }
                temp.add(t);
                left = false;
            }else if(c == ','){
                continue;
            }else {

                if (left) {
                    // 形如{a,b}c{d,e}中的a,b和d,e
                    queue.add(c);
                }else{
                    // 形如{a,b}c{d,e}中的c
                    List<Character> t = new ArrayList<>();
                    t.add(c);
                    temp.add(t);
                }
            }
        }
    }

    void backtrack(int start, List<List<Character>> temp, StringBuilder s, List<String> res){
        if(start>temp.size()){
            return;
        }else if(start==temp.size()){
            res.add(new String(s));
            return;
        }
        for(char c: temp.get(start)){
            s.append(c);
            backtrack(start+1, temp, s, res);
            s.deleteCharAt(s.length()-1);
        }

    }
}