LeetCode-Go 题解 | 394. Decode String 字符串解码：栈式解法与源码逐行剖析

导读

本文围绕 LeetCode 第 394 题 "Decode String"（字符串解码）展开，完整讲解编码规则 k[encoded_string] 的含义、三种典型嵌套/并列输入示例，并结合 LeetCode-Go 仓库中 394. Decode String.go 的官方实现，逐行剖析基于栈的解码流程，重点说明"重复数字可能为多位数"这一关键细节，同时对比同仓库 880. Decoded String at Index 的递归解法差异。读完本文，你将掌握用单栈完成字符串解码的标准套路，并能在本地通过 gotest.sh 复现测试验证。

题目描述

Given an encoded string, return its decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won't be input like 3a or 2[4].

中文大意：给定一个经过编码的字符串，返回它解码后的字符串。编码规则为 k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意：

• k 保证为正整数；
• 输入字符串总是有效的：没有额外空格，方括号总是符合格式要求（well-formed）；
• 原始数据不包含数字，数字只表示重复次数 k，因此不会出现像 3a 或 2[4] 这样的非法输入。

三个典型示例

原文档给出的三个示例覆盖了"并列重复"与"嵌套重复"两类核心场景：

s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

• 3[a]2[bc]：两个独立的重复块并列拼接，结果为 aaa + bcbc = aaabcbc；
• 3[a2[c]]：嵌套结构，内层 2[c] 先展开为 cc，外层 a2[c] 变为 acc，再重复 3 次得到 accaccacc；
• 2[abc]3[cd]ef：重复块与普通字母 ef 混合，结果为 abcabccdcdcdef。

仓库测试文件 394. Decode String_test.go 中还额外覆盖了一个多位数重复次数的用例 10[a] → aaaaaaaaaa，验证了实现能正确处理 k 大于等于 10 的情况（该用例不在 LeetCode 原题示例中，是仓库为强化覆盖而补充的）。

解题思路：用栈处理重复展开

原文档明确指出：这一题和第 880 题大体类似，用栈处理。核心思路可以概括为：

1. 遇到 [ 之前，把普通字符和数字依次压入栈中；
2. 遇到 ]，说明一个编码块结束，需要出栈直到栈顶为 [，收集到完整的 encoded_string；
3. 解析重复次数 k：由于数字可能存在多位（例如 10[a]），需要从 [ 之前的位置继续向前扫描，把连续的数字字符拼接起来再整体转换成整数；
4. 将 encoded_string 重复 k 次后重新压回栈中，替代原来被弹出的那一段；
5. 遍历完整个输入后，把栈中剩余的所有字符串片段依次串联，即为最终解码结果。

为什么用栈而不是递归展开？

栈天然匹配"嵌套结构"的处理顺序：内层 ] 总是先于外层 ] 被处理，恰好符合后进先出的性质，无需维护递归深度，也无需为每一层重复扫描整个字符串。

源码级实现剖析

仓库中的核心实现在 394. Decode String.go，完整代码如下：

package leetcode

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
}

下面按执行顺序逐段拆解：

第一段：入栈与触发条件

stack, res := []string{}, ""
for _, str := range s {
	if len(stack) == 0 || (len(stack) > 0 && str != ']') {
		stack = append(stack, string(str))
	} else {
		// 处理 ']' 触发的弹栈展开
	}
}

• 栈为空时无条件入栈；
• 栈非空且当前字符不是 ] 时同样入栈——注意这里数字、字母、[ 全部以单字符字符串的形式入栈，不做区分，统一交给后续处理；
• 只有当前字符是 ] 时才进入 else 分支执行解码逻辑。

这种"遇 ] 才处理"的写法，使得整个扫描过程只遍历输入一次，时间复杂度为 O(n)（不含展开后的结果长度）。

第二段：弹出编码块内容

tmp := ""
for stack[len(stack)-1] != "[" {
	tmp = stack[len(stack)-1] + tmp
	stack = stack[:len(stack)-1]
}
stack = stack[:len(stack)-1]

• 从栈顶开始依次弹出字符，直到栈顶为 [；
• 弹出的字符采用 tmp = 栈顶 + tmp 的前缀拼接方式，保证还原出的 encoded_string 顺序正确（因为后弹出来的是更靠前的字符）；
• 循环结束后把 [ 本身也弹出（stack = stack[:len(stack)-1]），此时 tmp 就是方括号内的原始编码串。

第三段：向前收集多位重复次数

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)

这是实现中最关键的细节（原文档特别强调）："重复的数字是可能存在多位的，所以需要往前找到不为数字的那一位，把数字转换出来"。

• 从 [ 弹出后的栈顶开始，向前（向栈底方向）连续检查是否为数字字符；
• 同样用 repeat = stack[index] + repeat 前缀拼接，例如栈中依次压入 1、0，则先弹出 0 再弹出 1，拼接结果为 "10"；
• 一旦遇到非数字字符立即 break，index 停在该非数字字符的下标；
• 最终通过 strconv.Atoi(repeat) 把多位数字字符串转换成整数 nums。

第四段：重复拼接并写回栈

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

• 先将 tmp 复制一份为 copyTmp，然后循环 nums-1 次累加，得到重复 nums 次后的完整字符串（之所以是 nums-1，是因为 tmp 本身已经是第一次的内容）；
• 随后把之前向前扫描到的那 len(repeat)-1 个数字字符从栈中弹出（保留最后一位数字所在位置，因为接下来要用结果覆盖它）；
• 最后 stack[index+1] = tmp，把展开后的字符串写回栈中 index+1 的位置，覆盖掉原来的数字位。这样嵌套场景下，外层继续遇到 ] 时就能以同样的流程把内层结果再次展开。

第五段：串联栈中所有片段

for _, s := range stack {
	res += s
}
return res

遍历结束后，栈中剩余的所有元素（普通字母、已经展开的字符串块）按顺序拼接，即为最终解码结果。以 3[a]2[bc] 为例，结束时栈中为 ["aaa", "bcbc"]，串联得到 aaabcbc。

测试验证：仓库用例全解析

394. Decode String_test.go 以表格驱动（table-driven）的方式组织了 4 组用例：

输入 s	期望输出	覆盖点
"10[a]"	"aaaaaaaaaa"	多位重复次数 k
"3[a]2[bc]"	"aaabcbc"	并列重复块拼接
"3[a2[c]]"	"accaccacc"	嵌套重复（内层先展开）
"2[abc]3[cd]ef"	"abcabccdcdcdef"	重复块与普通字符混合

测试中 para394 与 ans394 分别封装输入输出，Test_Problem394 遍历所有用例并打印 【input】 / 【output】 便于人工比对。嵌套用例 3[a2[c]] 正是对"第二段—第四段"循环逻辑的严格检验：内层 2[c] 先被展开为 cc 并写回栈，外层 3[a...] 再读取到 acc 并重复 3 次。

如何运行验证

仓库根目录的 gotest.sh 提供了对全部 leetcode 题解的统一测试命令：

go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...

也可单独运行本题测试：

go test -v ./leetcode/0394.Decode-String/

模块环境基于 go.mod（module github.com/halfrost/LeetCode-Go，Go 1.19+），仓库目标是 100% 测试覆盖率，因此每道题都配套了与本题相同风格的 _test.go 文件。

与第 880 题（Decoded String at Index）的对比

原文档特别提示"这一题和第 880 题大体类似"，二者共享"数字表示重复次数"的编码模型，但问题形态与解法取向不同：

• 394 题要求输出完整解码串，因此仓库实现选择显式栈 + 就地展开，把重复块完整物化后再拼回栈中；
• 880. Decoded String at Index 只要求返回第 K 个字符，若同样做全量展开会因解码串长度可能达到 2^63 量级而超时，所以 880. Decoded String at Index.go 采用递归 + 长度取模（K % length）的方式，在扫描过程中直接定位目标字符，避免了字符串展开。

由此可见：是否需要"完整展开"决定了 394 用栈、880 用递归取模，这是面对"编码字符串"类题目时最重要的决策依据。

复杂度分析

• 时间复杂度：O(n) 单次线性扫描输入，但注意展开后的结果字符串本身可能很长（如 10[a] 展开为 10 个字符），若把最终输出长度记为 m，实际总成本为 O(m) 级别；
• 空间复杂度：栈中存储了展开过程中的中间字符串片段，最坏情况下与最终结果长度同阶，为 O(m)。

小结

本题是"栈 + 字符串"双考点经典题。从仓库实现中可以提炼出三条可复用的经验：

1. 遇 ] 才处理，用 tmp = 栈顶 + tmp 的前缀拼接保证块内顺序；
2. 数字多位时向前连续扫描，用前缀拼接再统一 strconv.Atoi 转换，避免只处理个位数；
3. 展开结果写回栈内，天然支持任意层级的嵌套，无需额外递归深度标记。

配合 测试文件 中 4 组用例与 gotest.sh 一键运行脚本，你可以在本地直接验证上述每一步的正确性，并将其推广到其他同类编码字符串问题。