0020.有效的括号

难度：🟢 简单

标签：栈、字符串

链接：20. 有效的括号

题目描述

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

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。

2. 左括号必须以正确的顺序闭合。

3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"
输出：true

示例 2：

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

示例 3：

输入：s = "(]"
输出：false

解题思路

核心思想

本题是 栈 数据结构的经典应用场景。栈具有“后进先出”（LIFO）的特性，这与括号的嵌套匹配规则完美契合：越是后面遇到的左括号，就应该越早被匹配掉。

思路选择

我们可以遍历输入字符串：

• 当遇到一个左括号时，我们将其压入栈中，期待之后有对应的右括号来与之匹配。

• 当遇到一个右括号时，我们检查栈顶的元素。如果栈顶的左括号与当前右括号是匹配的一对，那么就将栈顶元素弹出，表示这对括号成功匹配。如果不匹配，或者栈为空（没有可匹配的左括号），则说明字符串无效。

关键步骤

1. 初始化：创建一个空栈 stack（在 JavaScript 中可用数组模拟），以及一个哈希表 map 用于存储右括号到左括号的映射关系，如 map = { ')': '(', '}': '{', ']': '[' }。

2. 遍历字符串：从头到尾遍历字符串 s 中的每一个字符。

3. 判断字符类型：

   • 情况一：是左括号。如果当前字符是 (, {, [ 之一，则将其压入 stack 中。

   • 情况二：是右括号。如果当前字符是 ), }, ] 之一，则执行匹配操作： a. 从 stack 中弹出一个元素。 b. 判断弹出的元素是否与当前右括号在 map 中对应的左括号相等。 c. 如果不相等，或者弹出前栈就是空的（pop() 返回 undefined），则说明不匹配，直接返回 false。

4. 最终检查：遍历完整个字符串后，检查 stack 是否为空。

   • 如果 stack 为空，说明所有左括号都已成功匹配，字符串有效，返回 true。

   • 如果 stack 不为空，说明还有未被匹配的左括号，字符串无效，返回 false。

代码实现

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
    // 使用数组作为栈
    const stack = [];
    // 建立右括号到左括号的映射
    const map = {
        ')': '(',
        '}': '{',
        ']': '['
    }

    for (let i = 0; i < s.length; i++) {
        const char = s[i];
        // 如果是左括号，入栈
        if (char === '(' || char === '{' || char === '[') {
            stack.push(char);
        } else {
            // 如果是右括号，判断栈顶元素是否匹配
            if (stack.pop() !== map[char]) {
                // 如果栈为空（pop返回undefined）或不匹配，则无效
                return false;
            }
        }
    }

    // 遍历结束后，栈应为空
    return stack.length === 0;
};

复杂度分析

• 时间复杂度：O(n) 其中 n 是字符串 s 的长度。我们只需要对字符串进行一次遍历。

• 空间复杂度：O(n) 在最坏的情况下，例如字符串全是左括号 ((((...，我们需要将所有 n 个字符都压入栈中，因此栈的空间消耗与 n 成正比。

相关题目

• 0022.括号生成

• 0032.最长有效括号

• 0071.简化路径

总结

本题通过栈这一数据结构，将一个看似复杂且涉及嵌套的匹配问题，转化为简单的入栈和出栈操作。这是算法中利用数据结构特性简化问题逻辑的典型案例。只要遇到涉及成对、嵌套或需要“最近匹配”的场景，都应优先考虑使用栈来解决。