有效的括号问题（LeetCode20）

题目描述

在这道题中，我们需要判断一个由括号组成的字符串是否有效。有效的字符串需满足以下条件：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

我们要处理的括号包括三种类型：( 和 ), { 和 }, 以及 [ 和 ]。例如：

• 示例 1：输入 "()"，输出 true
• 示例 2：输入 "()[]{}"，输出 true
• 示例 3：输入 "(]"，输出 false

解题思路

为了判断括号字符串是否有效，我们可以使用栈数据结构。栈具有先进后出的特点，非常适合处理成对出现的括号匹配问题。具体步骤如下：

1. 初始化一个空栈。
2. 遍历字符串中的每个字符：
   • 如果遇到左括号（(, {, [），则将其压入栈中。
   • 如果遇到右括号（), }, ]），则检查栈顶元素是否为对应的左括号。如果是，则弹出栈顶元素；否则，说明匹配失败，返回 false。
3. 遍历结束后，如果栈为空，说明所有的左括号都找到了对应的右括号，字符串有效；否则，说明有未匹配的左括号，字符串无效。

代码实现

以下是用 JavaScript 实现该思路的代码：

/**
 * @param {string} s
 * @return {boolean}
 */
const isValid = function (s) {
  const stack = [];
  const matchingBrackets = {
    ')': '(',
    '}': '{',
    ']': '[',
  };

  for (let i = 0; i < s.length; i++) {
    const char = s[i];
    if (char === '(' || char === '{' || char === '[') {
      stack.push(char); // 左括号入栈
    } else {
      if (stack.length === 0 || stack.pop() !== matchingBrackets[char]) {
        return false; // 栈为空或不匹配
      }
    }
  }
  
  return stack.length === 0; // 栈应为空表示所有括号均匹配
};

// 测试用例
console.log(isValid("()"));        // 输出: true
console.log(isValid("()[]{}"));    // 输出: true
console.log(isValid("(]"));        // 输出: false
console.log(isValid(""));          // 输出: true
console.log(isValid("{[]}"));      // 输出: true
console.log(isValid("([)]"));      // 输出: false

代码解释

1. 初始化栈：我们使用一个数组 stack 作为栈，用于存放左括号。
2. 定义匹配规则：创建一个对象 matchingBrackets，其中键是右括号，值是对应的左括号。
3. 遍历字符串：逐个检查字符串中的字符：
   • 如果是左括号，压入栈中。
   • 如果是右括号，检查栈顶元素是否为对应的左括号。如果匹配，则弹出栈顶元素；否则，返回 false。
4. 检查栈：遍历结束后，如果栈为空，则所有的括号均匹配，返回 true；否则，返回 false。

总结

通过上述方法，我们能够高效地判断括号字符串的有效性。利用栈这种数据结构，我们可以确保括号的正确匹配和顺序，从而解决了括号匹配问题。该方法的时间复杂度为 O(n)，其中 n 是字符串的长度，因为每个字符都仅被压入和弹出栈一次。这个方法简洁且高效，非常适合处理括号匹配的问题。