【每日算法】LeetCode 20. 有效的括号

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

LeetCode 20. 有效的括号：前端开发者的解析与实现

1. 题目描述

给定一个只包括'('，')'，'{'，'}'，'['，']'的字符串s，判断字符串是否有效。有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。

示例：

• 输入：s = "()"，输出：true
• 输入：s = "()[]{}"，输出：true
• 输入：s = "(]"，输出：false
• 输入：s = "([)]"，输出：false
• 输入：s = "{[]}"，输出：true

2. 问题分析

这是一个经典的括号匹配问题，在前端开发中广泛存在类似场景，例如：

• HTML/XML 标签闭合检查：确保<div>与</div>正确匹配。
• 代码编辑器语法高亮：在 JavaScript、CSS 或模板字符串中验证括号、引号是否成对。
• 表达式求值：如解析 JSON、计算算术表达式（如(1 + 2) * 3）时，需先验证括号有效性。

问题核心在于顺序匹配：后出现的左括号需先匹配右括号，这天然契合栈（Stack）的 LIFO（后进先出）特性。因此，栈是最优数据结构选择。

3. 解题思路

解决此问题主要有两种思路：暴力替换法和栈方法。栈方法是最优解，因其时间复杂度和代码可读性俱佳。

3.1 暴力法（替换法）

• 思路：不断循环替换字符串中成对的括号（如"()"、"[]"、"{}"）为空字符串，直到字符串不再变化。若最终字符串为空，则有效；否则无效。
• 复杂度：时间复杂度 O(n^2)（每次替换可能需遍历整个字符串），空间复杂度 O(1)。效率低，不推荐用于生产环境。

3.2 栈方法（最优解）

• 思路：遍历字符串，使用栈存储左括号；遇到右括号时，检查栈顶左括号是否匹配。若匹配则弹出栈顶，继续；否则无效。遍历结束后，栈应为空才有效。
• 复杂度：时间复杂度 O(n)，空间复杂度 O(n)（最坏情况栈存储所有字符）。这是最优解，因其一次遍历即可解决。

4. 代码实现

4.1 暴力法实现

functionisValid(s){while(s.includes('()')||s.includes('[]')||s.includes('{}')){s=s.replace('()','').replace('[]','').replace('{}','');}returns==='';}

4.2 栈方法实现

functionisValid(s){conststack=[];constmap={'(':')','[':']','{':'}'};for(letcharofs){if(map[char]){// 左括号入栈stack.push(char);}else{// 右括号检查匹配consttop=stack.pop();if(map[top]!==char){returnfalse;}}}// 栈为空表示所有括号匹配returnstack.length===0;}

5. 复杂度与优缺点对比

6. 总结

实际应用场景：

• 前端框架：Vue/React 的模板编译时，需检查标签和指令的括号匹配。
• 构建工具：Babel、Webpack 在解析 JavaScript AST 时，依赖括号验证。
• 开发工具：VS Code、Chrome DevTools 的代码调试器实时检测语法错误。
• 表单验证：复杂表达式输入（如规则引擎）需确保括号正确。