LeetCode 1087. 花括号展开

2024-09-22 HGNULB 约 11 分钟

文章信息 7 个分类 5 个标签

分类

题目描述

✅ 1087. 花括号展开

题意分析

输入是一个由小写字母、逗号和花括号组成的字符串。它可以被理解成若干个「槽位」从左到右串起来：一个裸露的字母是只有一种取值的槽位，一对花括号 {x,y,z} 是有多种取值的槽位。要求输出所有可能的字符串，也就是每个槽位各挑一个字母拼起来的全部组合，并且结果必须按字典序排列。

约束里有几条决定性的信息。花括号不会嵌套，这意味着不需要递归文法解析，一次从左到右的线性扫描就能把整个串切成槽位序列。花括号里的每一项都是单个小写字母，所以「解析一个选项」等价于「读一个字符」，不用处理多字符 token。字符串长度上限很小（五十以内），槽位数量因此有限，结果规模虽然是各槽位选项数的乘积，但在这个规模下完全可以把所有结果显式生成出来，说明这题考的是「把结构解析对、把组合枚举全」，而不是任何计数或压缩技巧。

边界有三处需要留意：花括号内部的字母不保证已经排好序，题目给的例子里就出现过 {b,a} 这种形式，所以不能假设扫描顺序就是字典序；输入可能完全没有花括号，此时答案只有一个字符串；单个花括号里也可能只有一个字母，退化成和裸字母等价的槽位，代码不该为它单开分支。

解法：逐段展开

核心思路

最直接的想法是回溯：写一个递归函数，参数是「当前解析到的下标」和「已经拼好的前缀」，遇到字母就把它接到前缀上往后递归，遇到花括号就先把括号内的所有字母收集出来，对每个字母各递归一次。这个做法是对的，但它有个不太舒服的地方：解析下标的推进逻辑和递归的分支逻辑纠缠在一起，写在白板上很容易把「括号闭合后下标应该跳到哪」写错，而且每条分支都要把括号重新解析一遍，做了大量重复的解析工作。

换个角度观察这个结构：由于花括号不嵌套，整个串其实就是槽位的线性拼接，槽位之间是完全独立的——第二个槽位选什么，跟第一个槽位选了什么毫无关系。既然如此，就没必要用递归去表达这种独立性，直接按顺序把槽位一个个「乘」进结果集合即可，这就是笛卡尔积的迭代形式。解析只做一遍，组合过程变成纯粹的两层循环，逻辑上比回溯更平坦。

显式写出这个算法维护的不变量：设 res 是当前的结果集合，i 是解析指针，那么任意时刻恒有「res 恰好等于 s 的前缀 s[0..i) 所能展开出的全部字符串，不重不漏」。初始时 i = 0、res = [""]，空前缀只能展开出空串，不变量成立。每一轮从 i 处解析出一个完整槽位，得到它的候选字母列表 options，用 res × options 生成新的 res 并把 i 推到槽位之后，不变量依然成立——因为新前缀的任何展开结果，都唯一地分解为「旧前缀的某个展开」拼上「本槽位的某个候选」。当 i 走到串尾时，前缀就是全串，res 即为答案集合。

最后剩一个字典序的问题。上面的过程只保证结果集合正确，不保证有序：花括号内的字母顺序会原样传导到结果的相对顺序上，{b,a} 就会先产出 b 开头的串。与其在解析时对每个 options 排序（那样确实也能让生成顺序天然有序，因为前缀相同时后缀的顺序就是字典序），不如在最后对结果整体排一次序，逻辑更直白，也不依赖「前缀有序推出整体有序」这个需要额外论证的性质。

解题步骤

初始化 res 为只含空串的列表，解析指针 i = 0。用空串而不是空列表作为起点，是因为空列表在做笛卡尔积时会把一切都乘成空，而空串是拼接运算的单位元，能让第一个槽位自然地生成初始结果。

进入主循环，条件是 i < s.length()。每一轮的职责固定为两件事：解析出一个槽位的候选列表，然后用它更新 res。把这两件事严格分开，是为了让「不管槽位是裸字母还是花括号，后半段的合并代码完全一致」，避免写两套重复的乘积逻辑。

解析时先看 s.charAt(i) 是不是 {。如果是，先 i++ 跳过左括号，然后一路前进直到遇到 }，途中把非逗号的字符收进 options，最后再 i++ 跳过右括号。用「跳过所有逗号」而不是「按逗号切分」，是因为选项保证是单字符，遇到字母就收即可，不需要维护 token 缓冲区。两次 i++ 一个都不能少，否则指针会停在括号上导致死循环或误解析。

如果当前字符不是 {，说明是一个裸字母，直接把它作为唯一候选放进 options 并 i++。这条分支让裸字母和只有一个选项的花括号在后续处理上完全等价。

合并阶段新建一个 next 列表，外层遍历 res 中的每个前缀，内层遍历 options 中的每个候选，把拼接结果放进 next，最后令 res = next。必须新建列表而不是原地修改 res，否则一边遍历一边追加会读到本轮刚生成的元素，导致同一个槽位被重复乘上去。

全部解析完后对 res 做一次字典序排序再返回。排序放在最后而不是解析中途，是因为只有此时每个字符串才是完整的，中途排序对最终顺序没有任何保证。

以 s = "{a,b}c{d,e}f" 走一遍。初始 res = [""]，i = 0。第一轮，s[0] 是 {，i 推到 1，依次读到 a（收入）、,（跳过）、b（收入），i 停在 4 处的 }，再 i++ 变成 5，options = ["a","b"]，合并后 res = ["a","b"]。第二轮 i = 5，s[5] 是裸字母 c，options = ["c"]，i 变成 6，合并后 res = ["ac","bc"]——注意这里 options 只有一个元素，乘积等于给每个前缀统一追加一个字符，规模没有膨胀。第三轮 i = 6 又是 {，同样解析出 options = ["d","e"]，i 推到 11，合并后 res = ["acd","ace","bcd","bce"]，元素数从 2 翻到 4。第四轮 i = 11，裸字母 f，options = ["f"]，i 变成 12，res = ["acdf","acef","bcdf","bcef"]。循环退出，排序后顺序不变，返回这四个字符串。如果把输入换成 "{b,a}c"，第一轮的 options 会是 ["b","a"]，中途 res = ["bc","ac"] 是乱序的，正是最后那次排序把它纠正成 ["ac","bc"]。

代码实现

class Solution {
    // 遇到花括号时解析备选字符列表，与当前结果做笛卡尔积。
    public String[] expand(String s) {
        List<String> res = new ArrayList<>();
        res.add("");

        int i = 0;
        while (i < s.length()) {
            List<String> options = new ArrayList<>();

            if (s.charAt(i) == '{') {
                i++;
                while (i < s.length() && s.charAt(i) != '}') {
                    if (s.charAt(i) != ',') {
                        options.add(String.valueOf(s.charAt(i)));
                    }
                    i++;
                }
                i++;
            } else {
                options.add(String.valueOf(s.charAt(i)));
                i++;
            }

            List<String> next = new ArrayList<>();
            for (String prefix : res) {
                for (String opt : options) {
                    next.add(prefix + opt);
                }
            }
            res = next;
        }

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

func expand(s string) []string {
    // 遇到花括号时解析备选字符列表，与当前结果做笛卡尔积。
    res := []string{""}

    i := 0
    for i < len(s) {
        options := make([]string, 0)

        if s[i] == '{' {
            i++
            for i < len(s) && s[i] != '}' {
                if s[i] != ',' {
                    options = append(options, string(s[i]))
                }
                i++
            }
            i++
        } else {
            options = append(options, string(s[i]))
            i++
        }

        next := make([]string, 0)
        for _, prefix := range res {
            for _, opt := range options {
                next = append(next, prefix+opt)
            }
        }
        res = next
    }

    sort.Strings(res)
    return res
}

复杂度分析

时间复杂度：$O(k \cdot r \log r)$，其中 $r$ 为结果数量（等于各槽位候选数的乘积），$k$ 为单个结果的长度。解析只扫一遍原串是 $O(n)$；生成阶段每个最终结果都被逐字符构造出来，是 $O(k \cdot r)$；排序做 $O(r \log r)$ 次字符串比较，每次比较代价 $O(k)$，这一项主导了总量。

空间复杂度：$O(k \cdot r)$，凭的是必须把全部 $r$ 个长度为 $k$ 的结果同时保存下来才能排序并返回，其余只有一个大小不超过字符集的候选列表和几个指针。

关键点总结

只要子结构之间彼此独立、没有嵌套依赖，就可以把回溯改写成迭代的笛卡尔积。判断标准是问自己「后面的选择会不会受前面选择的影响」，答案是「不会」时，两层循环就够了，不必上递归。

用空串而不是空列表作为结果集合的初值，是所有增量式组合枚举的通用起手式：它是拼接运算的单位元，能让第一轮循环和后续循环走完全相同的代码路径。

解析和合并两个阶段要严格分离。解析只负责「把指针推到下一个槽位并产出候选列表」，合并只负责乘积，这样裸字母和花括号共用同一段合并代码，分支数量减半，白板上出错的机会也随之减半。

迭代地扩展集合时必须写进新容器再整体替换，绝不能一边遍历一边往同一个容器里追加，这是这类写法最典型的自我污染陷阱。

面试视角上，被问到这题应该主动说明两点：一是「花括号不嵌套」这条约束是选择线性扫描而非递归下降解析的依据，二是如果面试官追问嵌套情况（也就是 1096），解法必须换成递归文法解析并用集合去重，这两问基本就是这道题的全部考察意图。

顺序要求要单独当成一个阶段处理。生成过程只保证集合正确，字典序是额外的输出约束，把它放在最后一次排序里解决，比试图让生成顺序天然有序更稳妥，也更容易向面试官解释正确性。

易错点总结

错误写法：把 res 初始化成空列表 new ArrayList<>() 而不是含空串的列表。用例 "abc"，第一轮合并时外层循环一次都不执行，next 始终为空，最终返回空数组。

错误写法：解析花括号后忘记最后那个 i++，指针停在 } 上。用例 "{a,b}c"，下一轮读到 } 会走裸字母分支，把 } 当成一个候选字符拼进结果，输出 ["a}c","b}c"]。

错误写法：进入花括号分支后没有先 i++ 跳过 {。用例 "{a,b}"，内层循环第一次就读到 { 并把它收进 options，结果里混入括号字符，同时指针推进节奏全乱。

错误写法：内层解析循环的条件只写 s.charAt(i) != '}'，漏掉 i < s.length()。用例是任何以花括号结尾且解析出错导致越过右括号的情况，会抛出字符串下标越界异常。

错误写法：在合并阶段直接对 res 原地追加，写成 for (String prefix : res) res.add(prefix + opt);。用例 "{a,b}" 会在遍历中修改集合，Java 里直接抛 ConcurrentModificationException，Go 里则会读到本轮新加的元素并无限膨胀。

错误写法：合并时把两层循环写反，外层遍历 options、内层遍历 res，同时仍然原地覆盖 res。用例 "{a,b}{c,d}" 会漏掉部分组合，输出只有两个结果而不是四个。

错误写法：省掉最后的排序，认为按扫描顺序生成就是字典序。用例 "{b,a}c" 会输出 ["bc","ac"]，字典序不满足题目要求。

错误写法：改成在每次解析出 options 后对 options 排序，但仍然把结果原样返回且中途某个槽位是裸字母。这条本身可行，但如果只对花括号分支的 options 排序而漏掉整体校验，用例 "{b,a}" 单独测能过，"{c,a}{b,a}" 这类多槽位组合一旦合并顺序写反就会漏掉排序保护，输出乱序。

错误写法：把逗号也收进 options，即去掉 if (s.charAt(i) != ',') 判断。用例 "{a,b}" 会得到 ["a", ",", "b"] 三个候选，输出里出现含逗号的字符串。

错误写法：用 s.split("[{}]") 之类的正则一把切开来做。用例 "a{b,c}d" 切出的片段无法区分「这一段原本在括号里」还是「原本是裸字母」，空片段的产生位置也依赖实现细节，恢复槽位语义比手写指针扫描更容易出错。

相似题目

题目	难度	考察点
17. 电话号码的字母组合	中等	槽位候选来自固定映射表，是笛卡尔积最纯粹的形态
22. 括号生成	中等	候选由合法性剪枝动态决定，无法预先列成独立槽位
39. 组合总和	中等	元素可重复选取，靠剩余目标值剪枝而非固定槽位数
46. 全排列	中等	每层候选随已用集合变化，槽位之间不再独立
77. 组合	中等	靠起始下标单调递增来天然去重，不需要额外集合
93. 复原 IP 地址	中等	分段长度不定，切分点要配合数值合法性一起枚举
131. 分割回文串	中等	切分点合法性依赖回文判断，常配预处理表加速
394. 字符串解码	中等	括号可嵌套，必须用栈保存外层上下文再回填
726. 原子的数量	困难	嵌套括号加乘数下推，还要按字典序输出计数结果
784. 字母大小写全排列	中等	每个字母槽位固定两种取值，数字位则只有一种
1096. 花括号展开 II	困难	花括号可嵌套且含并集语义，需要递归文法解析并对结果去重