20. 有效的括号

LeetCode 原题链接

题目描述

给定只包含 ()、[]、{} 的字符串，判断括号是否按正确类型和顺序闭合。

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

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

题型判断

右括号必须与最近一个尚未匹配的左括号配对，符合“后进先出”，因此使用栈。

核心思路

  • 遇到左括号，把它压入栈中。
  • 遇到右括号，弹出最近一个左括号，并检查二者是否匹配；不匹配时立即失败。
  • 遍历结束后，栈必须为空。

用映射表保存每种左括号对应的右括号。通过 bracket in pairs 可以直接判断当前字符是否为左括号。

代码实现

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

  for (const bracket of s) {
    if (bracket in pairs) {
      stack.push(bracket);
      continue;
    }

    const openingBracket = stack.pop();

    if (pairs[openingBracket] !== bracket) {
      return false;
    }
  }

  return stack.length === 0;
};

复杂度与易错点

  • 时间复杂度：O(n)。
  • 空间复杂度：O(n)。
  • 第一个字符是右括号时，空栈 pop() 得到 undefined，会正确返回 false。
  • 遍历结束仍有左括号未匹配时必须返回 false。
  • 仅统计每种括号数量相等不够，顺序也必须正确。

变式：只要求同类型括号成对出现

如果题目不要求括号按照嵌套顺序闭合，只要求每个右括号都能找到一个在它之前出现的同类型左括号，那么：

({)}

也应当返回 true。其中 ( 和 ) 成对，{ 和 } 成对；虽然两组括号发生了交叉，但这个变式允许交叉匹配。

这时不能使用一个栈，因为栈要求最后出现的左括号最先闭合。可以分别记录每种左括号尚未匹配的数量：

var isPaired = function (s) {
  const counts = {
    "(": 0,
    "[": 0,
    "{": 0,
  };

  const openingByClosing = {
    ")": "(",
    "]": "[",
    "}": "{",
  };

  for (const bracket of s) {
    if (bracket in counts) {
      counts[bracket]++;
      continue;
    }

    const openingBracket = openingByClosing[bracket];

    // 对应的左括号尚未出现，当前右括号无法配对
    if (counts[openingBracket] === 0) {
      return false;
    }

    counts[openingBracket]--;
  }

  // 每种左括号都必须恰好匹配完
  return Object.values(counts).every((count) => count === 0);
};

例如：

isPaired("({)}"); // true，允许不同类型的括号交叉
isPaired(")(");   // false，右括号不能先于对应的左括号出现
isPaired("(()");  // false，存在未匹配的左括号

这个变式仍然只遍历一次字符串，时间复杂度为 O(n)。由于括号类型固定为三种，额外空间复杂度为 O(1)。