有效的括号

题目描述

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

有效字符串需满足：

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

示例

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

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

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

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

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

约束条件

• 1 <= s.length <= 10^4
• s 仅由括号 '()[]{}' 组成

我的解题过程

第一次尝试：基础栈实现

一开始想到这道题的核心思路就是用栈来解决。因为括号匹配有一个特点：最后出现的左括号，应该最先被匹配。这正好符合栈的”后进先出”特性。

基本思路是：

• 遇到左括号时，把它压入栈中
• 遇到右括号时，检查栈顶的左括号是否与之匹配
• 如果匹配就弹出栈顶，如果不匹配就直接返回 false
• 最后检查栈是否为空

function isValid(s: string): boolean {
  const map = {
    "(": ")",
    "{": "}",
    "[": "]",
  };

  let stack = [];
  let index = 0;
  let flag = true;

  while (index < s.length) {
    if (Object.keys(map).includes(s[index])) {
      stack.push(s[index]);
    } else if (map[stack[stack.length - 1]] === s[index]) {
      stack.pop();
    } else {
      return (flag = false);
    }
    index++;
  }

  return stack.length ? false : flag;
}

这个版本能解决问题，但代码写得有点冗余，还有一些可以改进的地方。

优化思路：简化逻辑

优化的关键点在于：

1. 使用 for...of 代替 while 循环：更简洁，不需要手动维护索引
2. 提前返回：不需要 flag 变量，发现不匹配立即返回 false
3. 类型声明：加上 TypeScript 类型，让代码更规范
4. 简化判断：检查栈顶匹配时，可以先 pop 再判断，逻辑更清晰

function isValid(s: string): boolean {
  const map: Record<string, string> = {
    "(": ")",
    "{": "}",
    "[": "]",
  };

  const stack: string[] = [];

  for (const ch of s) {
    if (map[ch]) {
      stack.push(ch);
    } else {
      const last = stack.pop();
      if (!last || map[last] !== ch) {
        return false;
      }
    }
  }

  return stack.length === 0;
}

这个版本的优势：

• 逻辑更清晰：一眼就能看出来是左括号入栈，右括号匹配
• 提前退出：一旦发现不匹配就立即返回，不用遍历完整个字符串
• 边界处理：通过 !last 检查，处理了右括号多于左括号的情况（比如 ")))"）

小结

这道题是栈这个数据结构的经典应用。括号匹配问题的核心就是利用栈的”后进先出”特性，确保最近的左括号与当前右括号配对。

关键要点：

1. 左括号入栈，右括号出栈匹配
2. 每次遇到右括号时，要检查栈是否为空（避免栈下溢）
3. 最后要检查栈是否为空（确保所有左括号都被匹配）