【每日算法】 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} */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. 各实现思路的复杂度、优缺点对比

6. 总结

6.1 算法核心要点

1. 栈的运用：处理嵌套结构是栈的典型应用场景
2. 状态管理：需要同时跟踪数字、字符串和嵌套层级
3. 遍历策略：一次遍历完成所有解析，保证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语法等都需要类似的解析技术。