9-有效的括号

题目

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

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。

2. 左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1:

输入: "()" 输出: true

示例 2:

输入: "()[]{}" 输出: true

示例 3:

输入: "(]" 输出: false

示例 4:

输入: "([)]" 输出: false

示例 5:

输入: "{[]}" 输出: true

解答

记得曾经取面试不问租房，ceo就问了我这道题，不过感觉更像是在教我，非常温柔耐心地拆解。。怕是我太菜了他都看不下去了吧。。😂

最后“讨论”出来的是，用堆栈。如果是左括号就入栈，右括号就拿出栈顶的括号看看，是否匹配。

因为只有三个括号，因此好像把key设置成右括号更方便一些

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
  if (s.length % 2) {
    return false;
  } else if (s.length === 0) {
    return true;
  }
  const BRACKETS = {                // 似乎key是右括号更方便
    ")": "(",
    "]": "[",
    "}": "{"
  };
  let stack = [];
  for (let i = 0; i < s.length; i++) {
    const str = s[i];
    if (!BRACKETS.hasOwnProperty(str)) {
      stack.push(str);
    } else {
      const top = stack.pop();
      if (top !== BRACKETS[str]) {
        return false;
      }
    }
  }
  if (stack.length !== 0) {        // 最后stack得为空
    return false;
  } else {
    return true;
  }
};

Runtime: 52 ms, faster than 90.76% of JavaScript online submissions forValid Parentheses.

Memory Usage: 33.8 MB, less than 83.04% of JavaScript online submissions for Valid Parentheses.

优化一下？

最后的判断可以精简一下：

if (stack.length !== 0) {    
  return false;
} else {
  return true;
}

// 可以简化成这样：
return stack.length === 0

增加一个边界条件：如果第一个字符是右括号，那么必然是false

const BRACKETS = {
  ")": "(",
  "]": "[",
  "}": "{"
};
/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
  if (s.length % 2 || BRACKETS.hasOwnProperty(s[0])) {
    return false;
  } ...
...

那么加了之后效果如何呢？

优化后的代码：

const BRACKETS = {
  ")": "(",
  "]": "[",
  "}": "{"
};
/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
  if (s.length % 2 || BRACKETS.hasOwnProperty(s[0])) {
    return false;
  } else if (s.length === 0) {
    return true;
  }

  let stack = [];
  for (let i = 0; i < s.length; i++) {
    const str = s[i];
    if (!BRACKETS.hasOwnProperty(str)) {
      stack.push(str);
    } else {
      const top = stack.pop();
      if (top !== BRACKETS[str]) {
        return false;
      }
    }
  }
  return stack.length === 0;
};

Runtime: 40 ms, faster than 99.86% of JavaScript online submissions forValid Parentheses.

Memory Usage: 33.7 MB, less than 96.05% of JavaScript online submissions for Valid Parentheses.

【其实感觉这个判断地很不稳定……有时40ms有时56ms……】