Bloomberg 嵌套 k[文本] 解码：多位次数与栈状态

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练语法是非负十进制整数紧跟 [内容]，内容可有嵌套和普通字母；裸数字不合法。
• 0[abc] 解为空，非法括号报错；若真实面试保证输入合法，可省校验。

解题路线

1. 扫描数字时累计 repeat=10×repeat+digit，注意 12[...] 不能按两次独立次数处理。
2. 遇 [ 时把 (此前文本,次数) 压栈，清空当前文本；遇 ] 时弹出并拼 prefix+count×current。
3. 普通字符追加到当前层；结束时栈必须空且无待消费数字。
4. 若解码结果巨大，不能只按编码长度估复杂度；可先算展开长度设输出上限，或用 rope/chunks 降重复拼接成本。

手动走一遍

2[a3[b]]：内层 3[b]→bbb，外层段成 abbb，再重复 2 次得 abbbabbb；12[xy] 应复制 xy 12 次。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def decode_brackets(encoded):
    """Decode k[contents] with nested groups; plain text is copied."""
    stack = []
    current = ""
    repeat = 0
    have_number = False
    for char in encoded:
        if "0" <= char <= "9":
            repeat = repeat * 10 + ord(char) - ord("0")
            have_number = True
        elif char == "[":
            if not have_number:
                raise ValueError("missing repeat count")
            stack.append((current, repeat))
            current, repeat, have_number = "", 0, False
        elif char == "]":
            if not stack or have_number:
                raise ValueError("unmatched bracket or number")
            prefix, count = stack.pop()
            current = prefix + count * current
        else:
            if have_number:
                raise ValueError("number must be followed by [")
            current += char
    if stack or have_number:
        raise ValueError("incomplete encoded string")
    return current

复杂度

至少 O(M) 输出时间/空间，M 为解码后长度；朴素字符串多次拼接在某些语言可能额外复制，应按语言实现选择 builder。

易错点与追问

容易失分的边界

• 只读一位重复次数。
• 内层闭合后丢外层前缀。
• 把输出复杂度仅写 O(编码长度)。
• 不定义不完整括号/裸数字。

继续深挖

• 输出可能达到 GB 级怎么办？
• 如何只求解码长度？
• 如何支持流式写文件而非整段存内存？