题目重点：按完整英文题面和另一篇 IC4 追记还原方括号重复规则，纠正“LC39”编号误写并用栈处理嵌套。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 合法输入只含英文字母、十进制重复次数与方括号，k 为正；字母可出现在括号外，数字只出现在 k 前。
- 展示的通用训练代码也检查部分非法输入；题目保证输入有效，故非法行为不作为原题要求。输出长度至多 10^5。
解题路线
- 扫描数字时累积多位 k；遇 [ 把当前已解码前缀和 k 压栈，再从空字符串开始解内部内容。
- 遇 ] 弹出上一层前缀与次数，把当前层内容重复 k 次并接回上一层。遇普通字母追加当前层。
- 栈深对应未闭合方括号层数；每次 ] 恢复上一层，最终栈空得到完整解码结果。输入保证合法时不必猜测 5abc 这类无方括号写法。
- 若输出长度上界未知，拼接可能产生巨大内存，应在重复前累计长度并限制；本题上界 10^5 可直接构造。
手动走一遍
3[a2[c]] 先解内层 2[c]→cc，再形成 acc，外层重复三次得 accaccacc。题目明确 5abc 不应视作合法编码，不能用简单数字后取下一个字母的规则代替。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def decode_string(encoded):
"""Decode nested k[text] groups; letters outside groups pass through."""
if not isinstance(encoded, str):
raise ValueError("encoded must be a string")
stack = []
current = []
count = 0
has_count = False
for char in encoded:
if char.isdigit():
count = count * 10 + int(char)
has_count = True
elif char == "[":
if not has_count:
raise ValueError("missing repeat count")
stack.append((current, count))
current = []
count = 0
has_count = False
elif char == "]":
if has_count or not stack:
raise ValueError("unbalanced or misplaced bracket")
previous, repeat = stack.pop()
current = previous + ["".join(current) * repeat]
else:
if has_count or not (char.isascii() and char.isalpha()):
raise ValueError("invalid encoded character")
current.append(char)
if stack or has_count:
raise ValueError("incomplete encoded string")
return "".join(current)
复杂度
输入长度 N、输出长度 M，扫描与构造约 O(N+M) 时间、O(N+M) 空间；嵌套深度 D 贡献 O(D) 栈。Python 字符串重复创建量仍受 M 上界约束。
易错点与追问
容易失分的边界
- 依据错误的 LC39 标号按 Combination Sum 准备，而忽略帖中完整字符串题面。
- 把 5abc、6d 当合法示例，与题目指出的方括号规则冲突。
- 只处理单层或一位重复次数，嵌套时前缀丢失。
继续深挖
- 若输出可能达到数 GB，如何做长度检查、流式输出或懒展开？
- 如果原文字母允许数字，语法要如何改变才能无歧义？
