【每日算法】 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 栈解法（最优解）
使用两个栈分别存储数字和字符串：
- 遍历输入字符串的每个字符
- 遇到数字时，解析完整的数字（可能有多位）
- 遇到左括号
[时，将当前数字和字符串分别入栈，并重置 - 遇到右括号
]时，从栈中弹出数字和之前的字符串，构建当前字符串 - 遇到字母时，直接追加到当前字符串
时间复杂度：O(n)，其中 n 是解码后字符串的长度
空间复杂度：O(n)，最坏情况下栈的深度与嵌套深度成正比
3.2 递归解法（DFS）
利用递归天然处理嵌套结构：
- 遇到数字时，解析数字和括号内的子字符串
- 递归解码子字符串
- 将解码结果重复指定次数
- 继续处理后续字符
时间复杂度：O(n)
空间复杂度：O(n)，递归调用栈的深度
最优解推荐：栈解法。虽然两种方法的时间复杂度相同，但栈解法避免了递归的函数调用开销，且代码结构更清晰直观。
4. 代码实现
4.1 栈解法实现
/** * 栈解法 - 最优解 * @param {string} s * @return {string} */constdecodeString=function(s){letnumStack=[];// 存储数字的栈letstrStack=[];// 存储字符串的栈letnum=0;// 当前数字letresult='';// 当前字符串for(letcharofs){if(!isNaN(char)){// 如果是数字，累加（处理多位数字）num=num*10+parseInt(char);}elseif(char==='['){// 遇到左括号，将当前数字和字符串入栈numStack.push(num);strStack.push(result);// 重置数字和字符串num=0;result='';}elseif(char===']'){// 遇到右括号，出栈并构建字符串constrepeatTimes=numStack.pop();constprevStr=strStack.pop();result=prevStr+result.repeat(repeatTimes);}else{// 普通字母，直接追加result+=char;}}returnresult;};4.2 递归解法实现
/** * 递归解法 * @param {string} s * @return {string} */constdecodeStringDFS=function(s){letindex=0;constdfs=()=>{letresult='';letnum=0;while(index<s.length){constchar=s[index];if(!isNaN(char)){// 解析数字num=num*10+parseInt(char);index++;}elseif(char==='['){// 遇到左括号，递归处理子字符串index++;// 跳过 '['constinnerStr=dfs();result+=innerStr.repeat(num);num=0;// 重置数字}elseif(char===']'){// 遇到右括号，返回当前结果index++;// 跳过 ']'returnresult;}else{// 普通字符result+=char;index++;}}returnresult;};returndfs();};5. 各实现思路的复杂度、优缺点对比
| 方法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|---|---|
| 栈解法 | O(n) | O(n) | 1. 逻辑清晰直观 2. 无递归开销 3. 易于调试和跟踪 | 1. 需要维护两个栈 2. 代码相对较长 | 通用场景，特别是嵌套层数较深的情况 |
| 递归解法 | O(n) | O(n) | 1. 代码简洁 2. 利用调用栈自然处理嵌套 3. 符合问题本质（DFS） | 1. 递归深度受限 2. 可能栈溢出 3. 调试相对困难 | 嵌套层数可控，代码简洁性优先的场景 |
6. 总结
6.1 算法核心要点
- 栈的运用：处理嵌套结构是栈的典型应用场景
- 状态管理：需要同时跟踪数字、字符串和嵌套层级
- 遍历策略：一次遍历完成所有解析，保证O(n)时间复杂度
6.2 在前端开发中的实际应用场景
6.2.1 模板引擎解析
// 类似 Vue/React 的模板语法解析consttemplate="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）处理
// 多语言字符串中的变量替换和嵌套consti18nString="{count, plural, =0 {No messages} =1 {One message} other {# messages}}";6.2.5 富文本编辑器
处理嵌套的HTML标签、Markdown语法等都需要类似的解析技术。