LeetCode [1087] Brace Expansion

 1087. Brace Expansion

Medium

A string S represents a list of words.

Each letter in the word has 1 or more options.  If there is one option, the letter is represented as is.  If there is more than one option, then curly braces delimit the options.  For example, "{a,b,c}" represents options ["a", "b", "c"].

For example, "{a,b,c}d{e,f}" represents the list ["ade", "adf", "bde", "bdf", "cde", "cdf"].

Return all words that can be formed in this manner, in lexicographical order.

 

Example 1:

Input: "{a,b}c{d,e}f"
Output: ["acdf","acef","bcdf","bcef"]

Example 2:

Input: "abcd"
Output: ["abcd"]

 

Note:

1. 1 <= S.length <= 50
2. There are no nested curly brackets.
3. All characters inside a pair of consecutive opening and ending curly brackets are different.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

class Solution { List<String> ret = new ArrayList<>(); List<List<Character>> list = new ArrayList<>(); public String[] expand(String S) { int n = S.length(), i = 0; while(i<n){ list.add(new ArrayList<>()); if(Character.isAlphabetic(S.charAt(i))){ list.get(list.size()-1).add(S.charAt(i)); i++; }else{//{ i++;//skip '{' while(i<n && S.charAt(i)!='}'){ if(Character.isAlphabetic(S.charAt(i))) list.get(list.size()-1).add(S.charAt(i)); i++; } i++;//skip '{' } } helper(0, ""); return ret.toArray(new String[0]); } void helper(int i, String cur) { if (i == list.size() && cur.length() > 0) { ret.add(cur); } else if (list.get(i).size() == 0) { helper(i + 1, cur); } else { Collections.sort(list.get(i)); for (char c : list.get(i)) { helper(i + 1, cur + c); } } } }