LeetCode 1096. 花括号展开 II

2022-02-03 HGNULB 约 8 分钟

文章信息 6 个分类 6 个标签

分类

LeetCode CodeTop 困难未解决 1-2 微软

题目描述

✅ 1096. 花括号展开 II

题意分析

表达式由小写字母、花括号和逗号组成。逗号分隔的分支表示取并集，相邻的片段表示从各片段中各选一个字符串，再依次拼接；花括号可以嵌套，用来界定一组表达式。

返回整个表达式能够生成的全部字符串，重复结果只保留一次，最后按字典序排列。字母的原有先后顺序不能重排，只有分支选择产生不同结果。输入保证符合题目语法，不需要把它当作任意文本做纠错解析。

解法：递归解析表达式

核心思路

[!blue]

先明确两种操作的区别：并集把多份候选放在一起，拼接则要枚举左右候选的所有组合。相邻片段应先连成一个完整项，再与逗号另一侧的项取并集，所以解析也按优先级拆成三层。

parseExpr 解析由逗号连接的若干项，返回它们的并集；parseTerm 解析一串相邻因子，返回拼接结果；parseFactor 解析一个连续字母串，或一对花括号中的完整表达式。每一层返回的都是“当前片段可能生成的字符串集合”，统一了普通词和嵌套表达式的处理方式。

拼接两个集合时，对左集合中的每个 a 和右集合中的每个 b 生成 a + b，放入新的集合。一个项开始时使用只含空字符串的集合，因为空字符串与第一个因子拼接仍得到该因子；若使用空集合，第一轮就没有任何组合，后续也无法生成结果。

所有递归层共享一个游标，但分隔符各有负责者。term 遇到逗号或右括号就停止，不消耗它；expr 消耗逗号并开始下一个项；factor 遇到左括号时先越过它，递归解析内部表达式，返回后再越过对应右括号。因此内层返回时，外层总能从正确的下一个字符继续。

集合在每次并集和拼接时自然去重，不需要为生成路径另建去重规则。拼接必须写入新集合，避免一边枚举已有结果一边把新结果加入同一集合，混淆当前阶段与下一阶段。

全部解析结束后，才把最终集合转成列表并排序。中间候选的存放顺序不会影响并集或拼接的含义，无需在每次递归中重复排序。

解题步骤

用游标零调用 parseExpr，开始解析整个表达式。

表达式层先解析一个项，再对每个逗号后的项取并集。

项层从只含空字符串的集合出发，反复读取因子并做笛卡尔积拼接。

因子层读取连续字母；遇到左括号则递归解析内部，并消费对应右括号。

最终集合转为列表，按字典序排序后返回。

代码实现

class Solution {
    public List<String> braceExpansionII(String expression) {
        int[] idx = new int[1];
        Set<String> res = parseExpr(expression, idx);
        List<String> list = new ArrayList<>(res);

        Collections.sort(list);

        return list;
    }

    // expr = term (',' term)*，逗号表示并集。
    private Set<String> parseExpr(String s, int[] idx) {
        Set<String> res = parseTerm(s, idx);

        while (idx[0] < s.length() && s.charAt(idx[0]) == ',') {
            idx[0]++;
            res.addAll(parseTerm(s, idx));
        }

        return res;
    }

    // term = factor+，相邻表示笛卡尔积拼接，初值取单位元 {""}。
    private Set<String> parseTerm(String s, int[] idx) {
        Set<String> res = new HashSet<>();

        // 空字符串是拼接的单位元，空集合会让所有结果消失。
        res.add("");

        while (idx[0] < s.length() && s.charAt(idx[0]) != '}' && s.charAt(idx[0]) != ',') {
            Set<String> next = parseFactor(s, idx);
            // 用新集合接收拼接结果，避免一边遍历一边修改原集合。
            Set<String> merged = new HashSet<>();

            for (String a : res) {
                for (String b : next) {
                    merged.add(a + b);
                }
            }

            res = merged;
        }

        return res;
    }

    // factor 可能是单词或 {expr}。
    private Set<String> parseFactor(String s, int[] idx) {
        Set<String> res = new HashSet<>();

        if (s.charAt(idx[0]) == '{') {
            idx[0]++;
            // 左花括号已消耗，递归解析后还要跳过对应右花括号。
            res = parseExpr(s, idx);
            idx[0]++;

            return res;
        }

        StringBuilder sb = new StringBuilder();

        while (idx[0] < s.length()) {
            char c = s.charAt(idx[0]);

            if (c == '{' || c == '}' || c == ',') {
                break;
            }

            sb.append(c);
            idx[0]++;
        }

        res.add(sb.toString());

        return res;
    }
}

import "sort"

func braceExpansionII(expression string) []string {
    idx := 0
    res := parseExpr(expression, &idx)
    list := make([]string, 0, len(res))
    for k := range res {
        list = append(list, k)
    }
    sort.Strings(list)
    return list
}

// expr = term (',' term)*，逗号表示并集。
func parseExpr(s string, idx *int) map[string]struct{} {
    res := parseTerm(s, idx)
    for *idx < len(s) && s[*idx] == ',' {
        *idx = *idx + 1
        term := parseTerm(s, idx)
        for k := range term {
            res[k] = struct{}{}
        }
    }
    return res
}

// term = factor+，相邻表示笛卡尔积拼接，初值取单位元 {""}。
func parseTerm(s string, idx *int) map[string]struct{} {
    // 空字符串是拼接的单位元，空集合会让所有结果消失。
    res := map[string]struct{}{"": {}}
    for *idx < len(s) && s[*idx] != '}' && s[*idx] != ',' {
        next := parseFactor(s, idx)
        // 用新集合接收拼接结果，避免一边遍历一边修改原集合。
        merged := make(map[string]struct{})
        for a := range res {
            for b := range next {
                merged[a+b] = struct{}{}
            }
        }
        res = merged
    }
    return res
}

// factor 可能是单词或 {expr}。
func parseFactor(s string, idx *int) map[string]struct{} {
    res := make(map[string]struct{})
    if s[*idx] == '{' {
        *idx = *idx + 1
        // 左花括号已消耗，递归解析后还要跳过对应右花括号。
        res = parseExpr(s, idx)
        *idx = *idx + 1
        return res
    }

    start := *idx
    for *idx < len(s) {
        c := s[*idx]
        if c == '{' || c == '}' || c == ',' {
            break
        }
        *idx = *idx + 1
    }
    res[s[start:*idx]] = struct{}{}
    return res
}

复杂度分析

设输入长度为 n，所有拼接阶段累计尝试的候选数为 P，候选最大长度为 L，最终不同结果数为 K。

时间复杂度：期望 $O(n + PL + KL\log K)$，分别来自游标解析、字符串拼接与哈希去重、最终字典序排序。展开结果可能随输入长度指数增长，游标只扫一遍不代表整体为线性时间。

空间复杂度：$O(n + UL)$，U 为同时保留的中间和最终字符串数量；递归栈深度最坏为 $O(n)$。

关键点总结

[!green]

表达式、项、因子分层，对应并集、拼接、嵌套或字母三种职责。

每层返回字符串集合，空字符串是拼接单位元，空集合不是。

分隔符由指定层消费，集合负责去重，最外层排序负责输出顺序。

易错点总结

[!yellow]

用同一种操作处理逗号和相邻片段，会把并集与组合拼接混淆。

拼接初值为空集合，没有可与第一因子组合的元素，结果会始终为空。

项层没有在逗号处停止，因子层又无法消费逗号，会使游标停在原处。

内层表达式直接消费右括号，或者因子层忘记消费它，会使外层继续位置错乱。

遍历旧集合时直接加入拼接结果，可能混入当前轮新生成的字符串，应使用新的结果集合。

只去重没有排序，或只排序没有去重，分别无法满足输出的两项要求。

相似题目

题目	难度	关联与区别
1087. 花括号展开	中等	本题允许花括号嵌套，需要区分集合并与字符串连接，不能只按独立选项组展开。
394. 字符串解码	中等	同样递归解析嵌套结构，原题重复字符串，本题对字符串集合做并集与笛卡尔积。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2022/14174266

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！