LeetCode 有效的括号 JavaScript 栈实现题解

题目

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

有效字符串需满足：

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

解题思路

如此示例 {[]}，可以发现越靠后的左括号，右括号越靠前
满足后进先出的思想，可以考虑用栈

这个观察是整道题的关键。题目第二条要求「以正确的顺序闭合」，翻译过来就是：最近打开的那个括号，必须最先闭合。这跟栈的后进先出是同一件事，所以算法几乎是从数据结构的性质直接读出来的。

具体做法：遍历字符串，遇到左括号就压栈，表示「多了一个待闭合的」；遇到右括号就看栈顶，栈顶是当前最近未闭合的左括号，两者类型匹配就弹栈表示这一对配平了，不匹配直接判定无效。

有三种失败情形需要都覆盖到，漏掉任何一种都会错：

一是类型不匹配，比如 {]，栈顶是 { 却来了 ]。

二是右括号多了，比如 ())，最后那个 ) 来的时候栈已经空了，没有可配对的左括号。

三是左括号多了，比如 (()，遍历结束后栈里还剩东西。所以循环跑完不能直接返回 true，必须检查栈是否为空。

题解

开头 s.length % 2 === 1 那行是个小优化：括号必须成对，奇数长度的字符串一定不合法，可以直接返回，省掉整趟遍历。

<div id="leetCode-20"></button>

var isValid = function (s) {
  if (s.length % 2 === 1) return false;
  const tmp = [];
  for (var i = 0; i < s.length; i++) {
    const str = s[i];
    if ('(' === str || '{' === str || '[' === str) {
      tmp.push(str);
    } else {
      const lastElement = tmp[tmp.length - 1];

      if (
        (str === ')' && lastElement === '(') ||
        (str === ']' && lastElement === '[') ||
        (str === '}' && lastElement === '{')
      ) {
        tmp.pop();
      } else {
        return false;
      }
    }
  }
  return tmp.length === 0;
};

document.getElementById('leetCode-20').innerHTML +=
  '<br/>' + "isValid('{}')" + ': ' + isValid('{}');
document.getElementById('leetCode-20').innerHTML +=
  '<br/>' + "isValid('{]')" + ': ' + isValid('{]');
document.getElementById('leetCode-20').innerHTML +=
  '<br/>' + "isValid('{}[]')" + ': ' + isValid('{}[]');
document.getElementById('leetCode-20').innerHTML +=
  '<br/>' + "isValid('{[]}')" + ': ' + isValid('{[]}');

上面的示例把四种典型输入都跑了一遍，可以直接看到结果：{} 合法，{] 类型不匹配，{}[] 是并列的两对，{[]} 是嵌套的两对。

代码里 tmp[tmp.length - 1] 是取栈顶但不弹出，也就是通常说的 peek 操作。这里必须先看一眼再决定要不要弹，不能直接 pop——如果类型不匹配，弹出来就把栈破坏了。

栈为空时 tmp[tmp.length - 1] 得到的是 undefined，它不等于任何一个左括号，所以三个条件都不满足，直接走到 return false。这正好覆盖了前面说的第二种失败情形，不需要额外写空栈判断，算是个顺带的好处。

时间复杂度：O(n)
空间复杂度：O(n)

时间上每个字符处理一次，入栈出栈都是 O(1)。空间的最坏情况是全部都是左括号，比如 ((((((，栈里会存 n 个元素，所以是 O(n)。

题解优化用字典

上一版的问题在于那三个 || 连起来的判断：三种括号就要写三组条件，如果题目扩展到更多种成对符号，条件会线性增长，读起来也累。

改进思路是把「哪个左括号配哪个右括号」这层对应关系从代码逻辑里抽出来，变成数据。这样判断逻辑就只有一行，增减括号类型只需要动那张表。这是很通用的一个重构方向：用查表代替分支。

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

  const map = new Map([
    ['{', '}'],
    ['[', ']'],
    ['(', ')'],
  ]);
  const tmp = [];
  for (var i = 0; i < s.length; i++) {
    const str = s[i];
    if (map.get(str)) {
      tmp.push(str);
    } else {
      const lastElement = tmp[tmp.length - 1];

      if (map.get(lastElement) === str) {
        tmp.pop();
      } else {
        return false;
      }
    }
  }
  return tmp.length === 0;
};

这一版有两处很省的写法。

if (map.get(str)) 用来判断当前字符是不是左括号。因为表里只有左括号作为键，右括号查不到会返回 undefined，是假值，所以一次查表同时完成了「是否为左括号」的判断，不需要单独列举三个左括号。

map.get(lastElement) === str 是配对判断的核心：取出栈顶左括号应该配的右括号，跟当前字符比一下就行。栈为空时 lastElement 是 undefined，map.get(undefined) 返回 undefined，而 str 是一个具体字符，不相等，照样走到 return false。空栈的情况依然被覆盖了。

时间复杂度：O(n)
空间复杂度：O(n)

tip

Map 属于 O(1) 的空间复杂度

这个提示是说 Map 里只存了固定的三条映射，不随输入规模增长，所以它本身是常数空间。整体的 O(n) 来自栈，跟上一版一样。

补充一句，如果题目的字符串里还混有字母、数字等其他字符（本题限定只有六种括号，但有些变体题会放开），那么 else 分支就不能假定「不是左括号就一定是右括号」了，需要先跳过无关字符再处理。

题目

解题思路

题解

题解优化 用字典

题解优化用字典