在一种复杂的命令行系统中,命令的格式由一个模板字符串定义。模板由关键字、抉择结构 `{...}` 和可选结构 `[...]` 组成,元素间由空格分隔。
您的任务是解析这个模板,找出所有在顶层定义的固定关键字,并计算出每一个固定关键字在任意合法的命令中保证会出现的最小次数。
定义:
1. 关键字: 仅由小写字母组成的字符串。
2. 固定关键字: 在模板的顶层,不被任何括号包裹的关键字。它们是命令的根基。
3. 抉择结构 `{ A | B | ... }`: 表示该位置必须从选项 `A`, `B`, ... 中选择一个。选项本身可以是复杂的子模板。
4. 可选结构 `[ C ]`: 表示 `C` 部分是可选的,可以出现 0 次或 1 次。
保证出现次数的计算规则:
一个关键字 K 的“保证出现次数” C(K) ,是基于以下递归逻辑计算的:
- 首先,统计 K 作为固定关键字出现的次数。
- 然后,遍历模板中的所有抉择结构 `{ A | B | ... }`,如果 K 在每一个选项 A, B, ... 中都保证会出现(即,递归计算出的保证次数都 ≥ 1 ),那么这个抉择结构就为 C(K) 贡献 `+1`。
- 在可选结构 `[...]` 内部的任何关键字,都不被视为“保证出现”。- 输入为一行字符串,代表命令格式模板。
- 字符串由关键字、`{`, `}`, `|`, `[`, `]` 和空格组成。
- 输入字符串保证格式合法。
- 输出共两行。 - 第一行:按输入顺序,输出所有固定关键字,以单个空格分隔。 - 第二行:对应第一行的每个关键字,输出其保证出现的最小次数以单个空格分隔。
a b { c | d [ e ] } [ f { g | h } ]a b 1 1
考点:哈希
限制 1 秒 / 256MB | 标准输入输出
参考方向:哈希
用哈希表把「查找/计数」的开销降到 O(1) 均摊。
思路框架(哈希 通法 · 非本题专属)
实现要点:Python 用 dict / collections.Counter / defaultdict;C++ 用 unordered_map。
复杂度:时间 O(n) 均摊 | 空间 O(n)
该范式的通法易错点
本题在源数据中没有官方考点标签,方向由题面特征推断,仅供参考。
样例 1
a b { c | d [ e ] } [ f { g | h } ]a b / 1 1解析由校招宝本地引擎整理(依据源站考点标签 / 人工判题标注 / 题面规模信号),非官方题解,仅供思路参考。
本题来源:2025年秋招-华为-9月3号开发岗。