字符串解码

怎样从“s="3[a]2[bc]",解码为 "aaabcbc"。”推导出 栈 · 解码，并证明每次状态变化都不会漏掉答案？

中心结论：栈存(重复次数,已解码串);遇 [ 入栈,遇 ] 弹出重复展开。

给定一个经过编码的字符串，返回它解码后的字符串。编码规则为: k[encoded\_string]，表示其中方括号内部的 encoded\_string 正好重复 k 次。注意 k 保证为正整数。你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

在本站主例中，s="3[a]2[bc]",解码为 "aaabcbc"。

算法最终需要得到或观察："aaabcbc"。

每一步重新回看全部历史会重复；栈或队列只保存仍可能影响未来决策的状态。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“栈与队列轨道”，明确答案需要观察什么。
2. 2状态只维护 栈、当前串、数字缓冲。
3. 3转移每一步按照 栈存(重复次数,已解码串);遇 [ 入栈,遇 ] 弹出重复展开。
4. 4收尾读取 "aaabcbc"。，并复核边界与复杂度。

入栈/入队的不是所有历史，而是未来仍需要的信息。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：栈、当前串、数字缓冲。

这一题和第 880 题大体类似。用栈处理，遇到 "["，就要开始重复字符串了，另外重复的数字是可能存在多位的，所以需要往前找到不为数字的那一位，把数字转换出来。最后用把 stack 里面的字符串都串联起来即可。

栈存(重复次数,已解码串);遇 [ 入栈,遇 ] 弹出重复展开。

执行过程中持续维护：栈、当前串、数字缓冲。

正确性依赖以下不变量：栈层对应嵌套括号深度。

面试时可以压缩为：栈处理嵌套:数字+左括号入栈,右括号弹栈重复拼接。

落到当前题，执行机制可以压缩为：栈存(重复次数,已解码串);遇 [ 入栈,遇 ] 弹出重复展开。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入s="3[a]2[bc]",解码为 "aaabcbc"。 因为：栈存(重复次数,已解码串);遇 [ 入栈,遇 ] 弹出重复展开。
2. 2累积重复次数 k=3多位数字拼接。 因为：k 可能在 [ 之前多位。
3. 3遇到 '[',保存 k 与当前串进入嵌套层。 因为：外层状态被冻结在栈中。
4. 4字母 'a' 追加到当前串普通字符直接拼接。 因为：在当前括号层内累积。
5. 5遇到 '[',保存 k 与当前串进入嵌套层。 因为：外层状态被冻结在栈中。
6. 6']' 弹出:重复 'c' × 2当前层解码完成,拼回外层。 因为：栈还原嵌套结构。
7. 7']' 弹出:重复 'acc' × 3当前层解码完成,拼回外层。 因为：栈还原嵌套结构。
8. 8收尾与复杂度"aaabcbc"。 因为：时间 O(n) · 空间 O(1)。栈存(重复次数,已解码串);遇 [ 入栈,遇 ] 弹出重复展开。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

import (
	"strconv"
)

func decodeString(s string) string {
	stack, res := []string{}, ""
	for _, str := range s {
		if len(stack) == 0 || (len(stack) > 0 && str != ']') {
			stack = append(stack, string(str))
		} else {
			tmp := ""
			for stack[len(stack)-1] != "[" {
				tmp = stack[len(stack)-1] + tmp
				stack = stack[:len(stack)-1]
			}
			stack = stack[:len(stack)-1]
			index, repeat := 0, ""
			for index = len(stack) - 1; index >= 0; index-- {
				if stack[index] >= "0" && stack[index] <= "9" {
					repeat = stack[index] + repeat
				} else {
					break
				}
			}
			nums, _ := strconv.Atoi(repeat)
			copyTmp := tmp
			for i := 0; i < nums-1; i++ {
				tmp += copyTmp
			}
			for i := 0; i < len(repeat)-1; i++ {
				stack = stack[:len(stack)-1]
			}
			stack[index+1] = tmp
		}
	}
	for _, s := range stack {
		res += s
	}
	return res
}

func main() {
    // 1. 主例
    //    输入：mode="decode-string", text="3[a2[c]]"
    //    期望："aaabcbc"。
    //
    // 2. 失败 / 未命中
    //    检查：数字可能多位,要累积 parseInt。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC20 括号；LC385 迷你解析器
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意s="3[a]2[bc]",解码为 "aaabcbc"。
2. 2重复每一步重新回看全部历史会重复；栈或队列只保存仍可能影响未来决策的状态。
3. 3优化栈存(重复次数,已解码串);遇 [ 入栈,遇 ] 弹出重复展开。
4. 4证明栈层对应嵌套括号深度。
5. 5复杂度时间 O(n)，空间 O(1)