20. 有效的括号

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。

示例 1

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

示例 2

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

示例 3

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

示例 4

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

示例 5

输入：s = "{[]}"
输出：true

答案

var isValid = function(s) {
    const n = s.length

    // 奇数直接返回false
    if(n%2 === 1){
      return false
    }

    const pairs = new Map([
      [')','('], // 匹配')',返回'('
      [']','['], // 匹配']',返回'['
      ['}','{']  // 匹配'}',返回'{'
    ])

    // 栈：后入先出
    const stk = []

    for(let ch of s){
      if(pairs.has(ch)){
        // 添加判断条件：遍历到反方向符号，弹出检查是否为相对应的符号，不是则直接返回false
        if (!stk.length || stk[stk.length - 1] !== pairs.get(ch)) {
          return false;
        }
        stk.pop();
      }else{
        // 依次把'(' '[' '{' 正方向符号存入栈
        stk.push(ch);
      }
    }

    return !stk.length
};

isValid('()') // true

isValid('({)}') // false

20. 有效的括号

答案​

答案