详细介绍：【每日算法】 LeetCode 394. 字符串解码

对前端开发者而言，学习算法绝非为了“炫技”。它是你从“页面构建者”迈向“复杂系统设计者”的关键阶梯。它将你的编码能力从“实现功能”提升到“设计优雅、高效解决方案”的层面。从现在开始，每天投入一小段时间，结合前端场景去理解和练习，你将会感受到自身技术视野和问题解决能力的质的飞跃。------ 算法：资深前端开发者的进阶引擎

LeetCode 394. 字符串解码

1. 题目描述

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

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例 1：

输入：s = "3[a]2[bc]"
输出："aaabcbc"

示例 2：

输入：s = "3[a2[c]]"
输出："accaccacc"

示例 3：

输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"

示例 4：

输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"

2. 问题分析

这道题考察对嵌套结构的处理，非常类似于：

• HTML/XML 标签的嵌套解析
• JSON 字符串的解析
• 前端模板引擎中变量替换的嵌套场景
• 正则表达式中的分组引用

核心难点在于处理嵌套的括号和数字与字符串的对应关系。当遇到嵌套时，需要先解析内层的编码字符串，然后再与外层的数字相乘。

3. 解题思路

3.1 栈解法（最优解）

使用两个栈分别存储数字和字符串：

1. 遍历输入字符串的每个字符
2. 遇到数字时，解析完整的数字（可能有多位）
3. 遇到左括号 [ 时，将当前数字和字符串分别入栈，并重置
4. 遇到右括号 ] 时，从栈中弹出数字和之前的字符串，构建当前字符串
5. 遇到字母时，直接追加到当前字符串

时间复杂度： O(n)，其中 n 是解码后字符串的长度
空间复杂度： O(n)，最坏情况下栈的深度与嵌套深度成正比

3.2 递归解法（DFS）

利用递归天然处理嵌套结构：

1. 遇到数字时，解析数字和括号内的子字符串
2. 递归解码子字符串
3. 将解码结果重复指定次数
4. 继续处理后续字符

时间复杂度： O(n)
空间复杂度： O(n)，递归调用栈的深度

最优解推荐： 栈解法。虽然两种方法的时间复杂度相同，但栈解法避免了递归的函数调用开销，且代码结构更清晰直观。

4. 代码实现

4.1 栈解法实现

/**
* 栈解法 - 最优解
* @param {string} s
* @return {string}
*/
const decodeString = function(s) {
let numStack = [];    // 存储数字的栈
let strStack = [];    // 存储字符串的栈
let num = 0;          // 当前数字
let result = '';      // 当前字符串
for (let char of s) {
if (!isNaN(char)) {
// 如果是数字，累加（处理多位数字）
num = num * 10 + parseInt(char);
} else if (char === '[') {
// 遇到左括号，将当前数字和字符串入栈
numStack.push(num);
strStack.push(result);
// 重置数字和字符串
num = 0;
result = '';
} else if (char === ']') {
// 遇到右括号，出栈并构建字符串
const repeatTimes = numStack.pop();
const prevStr = strStack.pop();
result = prevStr + result.repeat(repeatTimes);
} else {
// 普通字母，直接追加
result += char;
}
}
return result;
};

4.2 递归解法实现

/**
* 递归解法
* @param {string} s
* @return {string}
*/
const decodeStringDFS = function(s) {
let index = 0;
const dfs = () => {
let result = '';
let num = 0;
while (index < s.length) {
const char = s[index];
if (!isNaN(char)) {
// 解析数字
num = num * 10 + parseInt(char);
index++;
} else if (char === '[') {
// 遇到左括号，递归处理子字符串
index++; // 跳过 '['
const innerStr = dfs();
result += innerStr.repeat(num);
num = 0; // 重置数字
} else if (char === ']') {
// 遇到右括号，返回当前结果
index++; // 跳过 ']'
return result;
} else {
// 普通字符
result += char;
index++;
}
}
return result;
};
return dfs();
};

5. 各实现思路的复杂度、优缺点对比

方法	时间复杂度	空间复杂度	优点	缺点	适用场景
栈解法	O(n)	O(n)	1. 逻辑清晰直观 2. 无递归开销 3. 易于调试和跟踪	1. 需要维护两个栈 2. 代码相对较长	通用场景，特别是嵌套层数较深的情况
递归解法	O(n)	O(n)	1. 代码简洁 2. 利用调用栈自然处理嵌套 3. 符合问题本质（DFS）	1. 递归深度受限 2. 可能栈溢出 3. 调试相对困难	嵌套层数可控，代码简洁性优先的场景

6. 总结

6.1 算法核心要点

1. 栈的运用：处理嵌套结构是栈的典型应用场景
2. 状态管理：需要同时跟踪数字、字符串和嵌套层级
3. 遍历策略：一次遍历完成所有解析，保证O(n)时间复杂度

6.2 在前端开发中的实际应用场景

6.2.1 模板引擎解析

// 类似 Vue/React 的模板语法解析
const template = "Hello {{user.name}}, you have {{notifications.count}} new messages";
// 内部实现可能使用类似的栈结构处理嵌套的 {{...}}

6.2.2 CSS 预处理

/* 类似 LESS/Sass 的嵌套规则解析 */
.container {
width: 100%;
.item {
color: red;
&:hover {
color: blue;
}
}
}

6.2.3 JSON/XML 解析器

前端常需要解析各种数据格式，理解栈在处理嵌套结构中的应用至关重要。

6.2.4 国际化（i18n）处理

// 多语言字符串中的变量替换和嵌套
const i18nString = "{count, plural, =0 {No messages} =1 {One message} other {# messages}}";

6.2.5 富文本编辑器

处理嵌套的HTML标签、Markdown语法等都需要类似的解析技术。