有效的括号匹配

问题

给定一个只包含 (、)、{、}、[、] 的字符串，判断字符串中的括号是否有效匹配。

有效的条件：

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

解答

function isValid(s) {
  // 奇数长度必定无效
  if (s.length % 2 !== 0) return false;

  // 括号映射：右括号 -> 左括号
  const map = {
    ')': '(',
    ']': '[',
    '}': '{'
  };

  const stack = [];

  for (const char of s) {
    if (char in map) {
      // 遇到右括号，检查栈顶是否匹配
      if (stack.pop() !== map[char]) {
        return false;
      }
    } else {
      // 遇到左括号，入栈
      stack.push(char);
    }
  }

  // 栈为空说明全部匹配
  return stack.length === 0;
}

测试用例

console.log(isValid('()'));       // true
console.log(isValid('()[]{}'));   // true
console.log(isValid('(]'));       // false
console.log(isValid('([)]'));     // false
console.log(isValid('{[]}'));     // true
console.log(isValid(''));         // true
console.log(isValid('('));        // false

另一种写法

function isValid(s) {
  const stack = [];
  const pairs = {
    '(': ')',
    '[': ']',
    '{': '}'
  };

  for (const char of s) {
    // 左括号入栈
    if (pairs[char]) {
      stack.push(char);
    } else {
      // 右括号：检查是否与栈顶左括号匹配
      const top = stack.pop();
      if (pairs[top] !== char) {
        return false;
      }
    }
  }

  return stack.length === 0;
}

关键点

• 使用栈结构，左括号入栈，遇到右括号时弹出栈顶检查是否匹配
• 用哈希表存储括号对应关系，避免多重 if-else
• 遍历结束后栈必须为空，否则有未闭合的左括号
• 奇数长度字符串可以直接返回 false（优化）
• 时间复杂度 O(n)，空间复杂度 O(n)