1087. Brace Expansion - Medium

偏执的太偏执、 2021-10-23 15:24 178阅读 0赞

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.

classical dfs

time = O(2^n), n -- \# of pair of braces, space = O(n)

class Solution {
        public String[] expand(String S) {
            if(S == null || S.length() == 0) {
                return new String[0];
            }
            List<String> list = new ArrayList<>();
            
            dfs(S, 0, new StringBuilder(), list);
            
            String[] res = new String[list.size()];
            for(int i = 0; i < list.size(); i++) {
                res[i] = list.get(i);
            }
            return res;
        }
        
        public void dfs(String s, int idx, StringBuilder sb, List<String> list) {
            if(idx == s.length()) {
                list.add(sb.toString());
                return;
            }
            int len = sb.length();
            
            if(s.charAt(idx) == '{') {
                List<Character> tmp = new ArrayList<>();
                int end = idx + 1;
                while(end < s.length() && s.charAt(end) != '}') {
                    if(Character.isLetter(s.charAt(end))) {
                        tmp.add(s.charAt(end));
                    }
                    end++;
                }
                Collections.sort(tmp);
                for(char c : tmp) {
                    sb.append(c);
                    dfs(s, end + 1, sb, list);
                    sb.setLength(len);
                }
            } else if(Character.isLetter(s.charAt(idx))) {
                sb.append(s.charAt(idx));
                dfs(s, idx + 1, sb, list);
            }
        }
    }

转载于:https://www.cnblogs.com/fatttcat/p/11220154.html