LeetCode 1087. 花括号展开

约 5 分钟
文章信息 8 个分类 5 个标签
分类
LeetCode CodeTop 中等 未解决 会员题 2-5 微软 拼多多
标签
字符串 排序 广度优先搜索 栈 回溯

题目描述

✅ 1087. 花括号展开

题意分析

字符串依次描述一个单词各位置的候选字母：普通字母只有一种选择，一对花括号里的字母是同一位置的多个选择。输入合法、花括号不嵌套，同组字母互不相同，要求返回全部展开结果并按字典序排序。

各位置的选择互不影响。只要在已有的每个前缀后，分别接上当前位置的每个候选，就能得到所有更长一位的前缀，因此可以边解析边逐段展开。

解法：逐段展开

核心思路

[!blue]

i 指向尚未解析的字符，options 保存当前位置可选的字母。遇到普通字母就读取一位；遇到左括号就读到对应右括号，收集字母并跳过逗号，最后再越过右括号。由于没有嵌套，不需要维护括号栈。

res 始终保存已经解析完的各位置所能组成的全部前缀。它初始包含一个空串，表示还未选择任何位置；若初始为空列表，第一轮就没有前缀可以扩展。

每轮把每个 prefix 与每个 opt 拼接到新的 next，完成后再用 next 替换 res。这样每个旧前缀恰好追加一个当前位置的候选，不会把本轮刚生成的前缀继续扩展。任意合法新前缀都能拆成旧前缀和当前字母，所以不会遗漏；同组字母不同、各前缀等长，也保证不会重复生成同一个单词。

解析结束后，每个前缀都已成为完整单词。候选字母在输入中不一定有序，因此最后统一排序，满足字典序要求。

解题步骤

  • 读裸字母，或读完整花括号并忽略逗号。
  • 对每个旧前缀与每个候选拼接。
  • 替换结果列表，全部结束后排序。

代码实现

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]);
    }
}

import "sort"

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
}

复杂度分析

设输入长度为 $n$，展开后单词长度为 $k$，处理完第 $j$ 个位置时有 $R_j$ 个前缀，最终结果数为 $R$。

  • 时间复杂度：$O(n+\sum_{j=1}^{k}jR_j+kR\log(R+1))$。解析扫描一次输入；第 $j$ 轮生成每个前缀需要复制 $j$ 个字符；排序时每次字符串比较最多查看 $k$ 个字符。
  • 空间复杂度：$O(kR+n)$，包含当前与下一轮的前缀集合、返回结果，以及解析当前候选所需的存储。

关键点总结

[!green]

  • 空串是拼接起点，空列表无法产生任何结果。
  • 各候选是单个字母，当前解析针对无嵌套语法。

易错点总结

[!yellow]

  • 跳过右括号的下标没有前进，会把括号当内容处理。
  • 把逗号也加入候选，会生成多余字符。
  • 未排序的候选会影响生成顺序，返回前需要满足排序要求。
  • 连续花括号表示连续的不同位置，需要依次拼接；没有花括号时，每轮只有一个候选，最终只得到输入单词本身。

相似题目

题目 难度 关联与区别
1096. 花括号展开 II 困难 本题花括号不嵌套，原题增加嵌套及集合并、连接的优先级，需要完整解析。
17. 电话号码的字母组合 中等 每一组选一个选项形成笛卡尔积，本题选项来自花括号，原题来自电话数字映射。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2024/41435667
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！