花括号展开

题目(LeetCode #1087)

花括号展开

给定一个表示单词列表的字符串 s 。单词中的每个字母都有一个或多个选项。

• 如果有一个选项，则字母按原样表示。
• 如果有多个选项，则用大括号分隔选项。例如, "{a,b,c}" 表示选项 ["a", "b", "c"] 。

例如，如果 s = "a{b,c}" ，第一个字符总是 'a' ，但第二个字符可以是 'b' 或 'c' 。原来的列表是 ["ab", "ac"] 。

请你 按字典顺序 ，返回所有以这种方式形成的单词。

示例1：

输入：s = “{a,b}c{d,e}f”
输出：[“acdf”,”acef”,”bcdf”,”bcef”]

示例2：

输入：s = “abcd”
输出：[“abcd”]

提示：

• 1 <= S.length <= 50
• s 由括号 '{}' , ',' 和小写英文字母组成。
• s 保证是一个有效的输入。
• 没有嵌套的大括号。
• 在一对连续的左括号和右括号内的所有字符都是不同的。

题解

class Solution {
    private char[] sArr;
    private List<String> result; // 用 List 存再排序比直接用 TreeSet 要快
    private StringBuilder builder;

    public String[] expand(String s) {
        sArr = s.toCharArray();
        result = new ArrayList<>();
        builder = new StringBuilder();

        dfs(0);

        Collections.sort(result);
        return result.toArray(new String[0]);
    }

    private void dfs(int idx) {
        if (idx == sArr.length) {
            result.add(builder.toString());
            return;
        }

        if (sArr[idx] == '{') {
            int rIdx = ++idx;
            while (rIdx < sArr.length && sArr[rIdx] != '}') rIdx++;

            for (int i = idx; i < rIdx; i++) {
                if (sArr[i] == ',') continue;
                builder.append(sArr[i]);
                dfs(rIdx + 1);
                builder.deleteCharAt(builder.length() - 1);
            }
        } else {
            builder.append(sArr[idx]);
            dfs(idx + 1);
            builder.deleteCharAt(builder.length() - 1);
        }
    }
}