20. 有效的括号

题目描述

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

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

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

题型判断

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

核心思路

遇到左括号，把对应的右括号压栈。
遇到右括号，它必须等于栈顶元素，否则立即失败。
遍历结束后，栈必须为空。

保存“期待出现的右括号”能让匹配判断更直接。

代码实现

var isValid = function (s) {
  if (s.length % 2 === 1) return false;

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

  for (const character of s) {
    if (closingByOpening[character]) {
      stack.push(closingByOpening[character]);
    } else if (stack.pop() !== character) {
      return false;
    }
  }

  return stack.length === 0;
};

复杂度与易错点

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

ON THIS PAGE

#20. 有效的括号

#题目描述

#题型判断

#核心思路

#代码实现

#复杂度与易错点

20. 有效的括号

题目描述

题型判断

核心思路

代码实现

复杂度与易错点