LeetCode 394 字符串解码：用栈解析 k[encoded_string] 嵌套编码（C++ 逐行详解）

本文基于 InterviewGuide 仓库中「精选力扣 300+ 道算法题」之栈专题（Medium）的原始题解整理扩充而成，完整解析 LeetCode 394「字符串解码」的栈解法原理、原版 C++ 实现与逐段推演，并横向对比递归、双栈等进阶思路，适合校招、社招笔试面试场景下的算法备考。

导读

字符串解码（Decode String）是力扣栈分类下的一道经典 Medium 题，也是字节、腾讯等互联网大厂笔试面试中出现频率较高的「括号+重复次数」型字符串处理题。它的核心难点在于编码规则 k[encoded_string] 支持任意层嵌套（如 3[a2[c]]），要求解读者在遇到右括号 ] 时，能够一次性弹出最近的左括号 [ 之前的所有字符，再按倍数 k 整体回填。读完本文，你将掌握：如何用单字符串模拟栈完成解码、为什么数字需要"反向收集再反转"、stod 在此处的特殊用法，以及递归/双栈等替代方案的取舍依据。

本文讲解的题解源码位于仓库 docs/notes/03-hunting_job/03-algorithm/03-leetcode/07-栈/medium/394.字符串解码.md，该文档属于 InterviewGuide「精选力扣300+道算法题」中按标签分类的栈专题题解。

一、题目与编码规则

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为 k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。题目保证：

• k 为正整数；
• 输入字符串总是有效的：没有额外的空格，方括号总是符合格式要求；
• 原始数据不包含数字，所有数字只表示重复次数 k，不会出现 3a 或 2[4] 这类输入。

示例

输入 s	解码结果	说明
"3[a]2[bc]"	"aaabcbc"	3[a] → aaa，2[bc] → bcbc，拼接得 aaabcbc
"3[a2[c]]"	"accaccacc"	内层 2[c] → cc，外层 3[a cc] → acc 重复 3 次
"2[abc]3[cd]ef"	"abcabccdcdcdef"	前缀 2[abc]、中段 3[cd]、后缀普通字符 ef 依次拼接

第二个示例揭示了本题真正的难点：嵌套括号。解码必须"从内到外"进行——先解最内层 2[c]，再解外层 3[a2[c]]。这种"先入后出、由内向外"的处理顺序，天然与栈（Stack）的 LIFO 特性吻合，因此栈是本题的主流解法。

二、核心思路：用栈模拟"从内到外"的解码过程

从编码规则可以看出，整个字符串由三类字符构成：

1. 字母（a-z）：普通字符，直接累积到结果；
2. 左括号 [：标记一组待重复内容的起点；
3. 右括号 ]：触发一次"解码动作"——把最近一组 k[encoded_string] 展开；
4. 数字（0-9）：出现在 [ 之前，表示重复次数 k。

算法的主干是一个大循环，逐字符扫描输入串，用结果字符串 res 充当"栈"：

• 遇到非 ] 字符（字母、数字、[），一律 push_back 到 res 尾部——此时 res 尾部就是"栈顶"；
• 遇到 ] 时，res 尾部一定是一个完整的 encoded_string + [ + k 结构，于是分三步处理：
  1. 收集待重复的内容：从 res 尾部不断 pop_back，直到遇到 [，把弹出来的字符存入临时串 temp（注意此时字符顺序是反的）；
  2. 弹出 [：把分隔符 [ 本身弹出；
  3. 收集重复次数：继续从 res 尾部弹出数字字符，得到反向的数字串 countStr，反转后得到整数 count；
  4. 回填：把 temp 反转回正序，重复 count 次追加回 res。

循环结束后，res 中所有括号都已被展开，剩下的就是解码结果。

用一句话概括：遇到 ] 就"弹出一段、乘以倍数、再压回去"，全程只用一个容器，利用它尾部操作的特性同时承担"字符栈"和"结果串"两种角色。

三、原版代码逐段解析（阿秀第一版，C++）

仓库文档中给出的第一版解法如下（为便于讲解，保留原文并补充注释）：

string decodeString(string s) {

	string res, temp, countStr;
	int count;

	for (auto i : s) {
		count = 0;
		temp = "";
		countStr = "";
		if (i != ']')
			res.push_back(i);
		else {
			while (res.back() != '[')//直到遇到了[
			{
				temp += res.back();
				res.pop_back();
			}
			res.pop_back();//将 [ 推出去

			while (!res.empty() && res.back() >= '0' && res.back() <= '9') {
				countStr += res.back();
				res.pop_back();
			}
			reverse(countStr.begin(), countStr.end());
			count = stod(countStr, 0);
			reverse(temp.begin(), temp.end());

			for (int j = 0; j < count; ++j) res += temp;
		}
	}
	return res;
}

3.1 主循环：普通字符直接入栈

for (auto i : s) {
    count = 0;
    temp = "";
    countStr = "";
    if (i != ']')
        res.push_back(i);
    ...
}

每次循环先重置三个局部变量（count、temp、countStr），保证处理 ] 时不会残留上一次的数据。只要当前字符不是 ]，就无条件压入 res 尾部。这一步对字母、数字、[ 一视同仁，它们的"身份"要等到遇到 ] 时才会被识别。

3.2 遇到 ]：弹出一段"编码内容"

while (res.back() != '[') {
    temp += res.back();
    res.pop_back();
}
res.pop_back();//将 [ 推出去

从 res 尾部逐个弹出字符并追加到 temp。由于栈是后进先出，这段内容被反序收集。例如栈内为 ... a c c [ 时（即 acc[ 的入栈形态），弹出的顺序是 c、c、a，temp = "cca"。随后再把 [ 弹出，完成"拆开编码单元"的动作。

3.3 收集重复次数 k

while (!res.empty() && res.back() >= '0' && res.back() <= '9') {
    countStr += res.back();
    res.pop_back();
}
reverse(countStr.begin(), countStr.end());
count = stod(countStr, 0);

紧跟着 [ 的入栈顺序必然是数字在前、[ 在后，因此弹出 [ 之后，res 尾部就是数字。注意数字也是被反序弹出的：2 先弹、3 后弹（若 k = 32），所以 countStr 是 "23"，必须 reverse 回 "32" 才能得到真实倍数。

此处原版代码使用了 stod(countStr, 0) 将字符串转成 double 再隐式赋给 int count。对于本题 k 为正整数、且不会有超大数溢出的前提下可以工作，但更规范的写法是 stoi 或 atoi——这一点在面试中值得主动提出优化。

3.4 反转内容并回填

reverse(temp.begin(), temp.end());
for (int j = 0; j < count; ++j) res += temp;

temp 在收集阶段是反序的，这里先 reverse 还原成正序，再连续追加 count 次。追加回 res 的字符可能是纯字母（如 bc），也可能是包含其他括号组的中间结果——外层嵌套正是靠"把展开后的内容重新压回栈顶，等待外层 ] 再次触发解码"来完成的。

3.5 复杂度分析

• 时间复杂度：O(N) 级别的线性扫描 + 每次 ] 触发的内容弹栈与回填。需要注意，同一个字符可能因多层嵌套被多次"弹出再压回"（每层 ] 处理一次），最坏情况下如 3[a3[a3[a]...]] 深嵌套串，总代价与"最终结果长度 × 嵌套深度"相关；对本题数据规模而言整体呈线性到近线性表现。
• 空间复杂度：O(N)，res 在最坏情况下需要暂存最终解码结果（N 为最终结果长度）。

四、模拟运行：以 3[a2[c]] 为例

下面逐步追踪输入 s = "3[a2[c]]" 的执行过程，帮助理解嵌套解码的闭环：

步骤	当前字符	操作	res 栈内容（→ 为栈顶方向）
1	3	入栈	3
2	[	入栈	3[
3	a	入栈	3[a
4	2	入栈	3[a2
5	[	入栈	3[a2[
6	c	入栈	3[a2[c
7	]	弹出 c→temp="c"，弹出 [；弹出 2→countStr="2"，反转得 count=2；temp 反转仍为 "c"，回填 2 次	3[a + cc → 3[acc
8	]	弹出 c,c,a→temp="cca"，弹出 [；弹出 3→count=3；temp 反转成 "acc"，回填 3 次	accaccacc
9	循环结束	返回	"accaccacc" ✓

可以看到，第 7 步完成内层 2[c] 展开后，cc 被压回栈顶，第 8 步外层 3[a2[c]] 解码时把 a 与 cc 一起弹出，合并为 acc 再乘以 3——嵌套逻辑由此闭环。这正是单栈解法的精妙所在：展开的中间结果始终停留在栈顶，天然等待下一层 ] 的处理。

五、易错点与面试追问

• 字符顺序的两次反转：temp 与 countStr 都是反向收集，必须各自 reverse 后再使用，漏掉任何一次都会得到错误结果。
• res.empty() 判空：收集数字时用 !res.empty() 保护，防止 k 位于整个字符串最开头、弹出数字后 res 已空时越界访问 res.back()。
• stod 与 stoi：原版用 stod（转 double）再隐式转 int，功能上可行但语义不严谨，面试时可主动改为 stoi(countStr)，并说明理由（k 为正整数，直接整数解析即可）。
• 为什么不用单独的 stack<char>：本解法用 string res 同时充当栈与结果容器，省去了"栈内字符→最终字符串"的二次搬运，是空间与代码量上的简化，代价是语义上不够直观；使用显式 stack<char> 同样可行，逻辑完全等价。
• 空内容 []：题目保证输入有效，k 为正整数，因此不会出现 0[...] 或空括号组；即便出现 []，本算法也会因 while 循环条件（res.back() != '['）在 [ 处立即停止、temp 为空，回填空串，不会崩溃。

六、进阶解法对比（供深入理解）

单栈解法之外，本题还有几种常见替代思路，面试中被追问"有没有其他做法"时可从容应对。

6.1 递归 / DFS：天然适配嵌套结构

编码结构本身就是递归定义的（encoded_string 内部可以再次出现 k[...]），因此可以写一个递归函数：用索引 i 指针扫描，遇到数字就解析出完整 k，遇到 [ 就递归解码内层，直到 ] 返回。递归解法把"栈帧"隐式交给系统调用栈，代码更贴合嵌套结构，但需要注意索引指针的全局传递与递归深度限制。

6.2 双栈：数字栈 + 字符串栈

显式使用 stack<int> numStack 与 stack<string> strStack：遇数字解析入数字栈，遇 [ 把当前累积串压入字符串栈并清空，遇 ] 弹出数字与前一累积串做拼接。双栈方案逻辑最直白、最容易被面试官认可，代价是代码量比单栈略长。

6.3 三种方案对比一览

方案	核心容器	优点	注意点
单字符串模拟栈（本文原版）	string res	代码简短、空间占用小	字符顺序需两次反转
双栈（数字栈 + 字符串栈）	stack<int> + stack<string>	逻辑直观、易解释	代码略长
递归 / DFS	系统调用栈	贴合嵌套结构、可读性好	注意索引传递与递归深度

七、同类题横向拓展（InterviewGuide 栈专题）

本题所在的栈专题目录还收录了多道与"括号处理、相邻消除、栈模拟"同源的高频题，建议按下面的顺序一起刷，形成"括号/重复类"题型的解题肌肉记忆：

• 1190. 反转每对括号间的子串：同样是"从内到外逐层处理括号"，解法与 394 高度同构，用 stack<char> 显式入栈，遇 ) 弹栈反转；
• 1209. 删除字符串中的所有相邻重复项 II：k 个相邻重复项消除，使用"字符栈 + 次数栈"双栈，是 394 双栈思路的变体；
• 71. 简化路径：用栈处理路径分段与 .. 回退，体会栈在"状态回溯"场景的普适性；
• 856. 括号的分数、921. 使括号有效的最少添加：括号类题目的计分与合法性维护。

八、面试场景要点小结

• 考点定位：本题考察"嵌套结构的线性化处理"，核心是识别出"遇到右括号触发一次逆序展开"这一事件驱动模型，属于栈应用的三个典型场景之一（括号匹配、逆序处理、历史回溯）。
• 手写要点：先把三类字符（字母/[/数字）的入栈规则说清楚，再强调遇到 ] 时的三步动作（弹内容→弹 [→弹数字），最后补上两次 reverse 与 res.empty() 判空的边界细节。
• 进阶话术：能主动对比单栈、双栈、递归三种解法，并指出 stod 可替换为 stoi，会给面试官留下"知其然且知其所以然"的印象。

本文内容基于 InterviewGuide 仓库 394.字符串解码.md 原始题解扩充整理，题解所属的「精选力扣 300+ 道算法题」专栏整体说明见 01-introduce.md，栈专题完整题目清单见 栈专题目录。