有效的括号（LeetCode中文版）

最近在LeetCode上做题碰到的这道题：

---

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

有效字符串需满足：

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

示例 1:

输入: “()” 输出: true

示例 2:

输入: “()[]{}” 输出: true

示例 3:

输入: “(]” 输出: false

示例 4:

输入: “([)]” 输出: false

示例 5:

输入: “{[]}” 输出: true

---

首先想到的是正则匹配，然后看了一下提示的解题思路，发现栈匹配的方法是非常不错的一个思路，于是实现了一下

第一次通过的代码

var isValid = function(s) {
    var a = s.split('')
    var b = []
    for(var i of a.keys()){
        if(['(','[','{'].includes(a[i])){
            b.push(a[i])
        }else{
            if(b.length===0){
                return false
            }else if((b[b.length-1].charCodeAt()+1===a[i].charCodeAt())||(b[b.length-1].charCodeAt()+2===a[i].charCodeAt())){
                b.pop()
            }else {
                return false
            }
        }
    }
    if(b.length!==0) return false
    return true
};

执行用时：1356ms，战胜了1.30%的JavaScript记录

判断右括号的时候非常搞笑地使用了Unicode编码做的判断，其实是不太好的，可能会匹配到非括号的字符，通过对象做映射会更好一些，中间嵌套的if…else语句也很多余，完全可以删掉

做完之后当晚刷奇舞团的公众号的时候就看到了这篇文章：

然后发现说的正好是这一道题，仔细看了实现，发现尾部return可以替换到我的代码中去，简约很多，于是就产生了

第二次修改

var isValid = function(s) {
    var a = s.split('')
    var b = []
    for(var i of a.keys()){
        if(['(','[','{'].includes(a[i])){
            b.push(a[i])
        }else{
            if(b.length===0){
                return false
            }else if((b[b.length-1].charCodeAt()+1===a[i].charCodeAt())||(b[b.length-1].charCodeAt()+2===a[i].charCodeAt())){
                b.pop()
            }else {
                return false
            }
        }
    }
    return b.length===0 //没错就只有这一部分，是不是简单得多
};

执行用时：80ms，战胜了54.02%的JavaScript记录

这次修改仅仅是将尾部的if语句替换成了直接返回一个恒等表达式，然后运行耗时不可同日而语，然后我又尝试替换成了一个三元运算符，时间增加到了96ms

看的我一脸懵逼，这里面有门道，要好好研究一下，这个我们后续再谈

然后作者提出了包含非括号字符的需求，根据作者的实现，我又修改了一次

第三次修改

var isValid = function(s) {
  const map = new Map([
  ['{','}'],
  ['[',']'],
  ['(',')']
  ])
  let a = []
  for(let i=0;i<s.length;i++){
    if(map.has(s[i])){
      a.push(s[i])
    }else if([...map.values()].includes(s[i])){
      if(map.get(a.pop())!==s[i]) return false
    }
  }
  return a.length===0
};

执行用时：84ms，战胜了44.14%的JavaScript记录

通过新的数据结构Map做的括号配对映射，核心部分相比作者的实现要简化了许多，直接通过pop方法的返回值结合Map实例的get方法判断是否返回false，如有不妥请指正