20. 有效的括号

题目

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。

例

输入: "()[]{}"

输出: true

题解

栈

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
  s = s.split("");
  let stack = [];
  const left = ["(", "{", "["];
  const right = [")", "}", "]"];
  while (s.length) {
    let x = s.shift();
    // 是左括号就入栈
    if (left.indexOf(x) > -1) {
      stack.push(x);
    } else {
      // 否则和栈顶元素比较
      let top = stack[stack.length - 1];

      // 如果匹配栈顶元素出栈
      if (left.indexOf(top) == right.indexOf(x)) {
        stack.pop();
      } else {
        // 不匹配返回
        return false;
      }
    }
  }
  // 如果栈为空则匹配成功
  return stack.length ? false : true;
};

精简写法:

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
  const ss = [];
  const a = { ")": 1, "]": 2, "}": 3 },
    b = { "(": 1, "[": 2, "{": 3 };
  for (var x of s) {
    if (a[x]) {
      if (b[ss.pop()] != a[x]) return false;
    } else ss.push(x);
  }
  return ss.length == 0;
};