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

有效字符串需满足：

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

示例 1：

输入：s = “()”

输出：true

示例 2：

输入：s = “()[]{}”

输出：true

示例 3：

输入：s = “(]”

输出：false

示例 4：

输入：s = “([])”

输出：true

提示：

  • 1 <= s.length <= 104
  • s 仅由括号 ‘()[]{}’ 组成

解题思路

这一题需要括号一定成对匹配，这可以利用栈的特点来解决，栈的特点就是先进后出，这样就可以将对应的括号进行成对匹配。

首先如果字符串的字符数为奇数，那么括号不可能成对，直接返回false。

我们可以创建一个栈Stack用于匹配字符，然后创建一个Map用于字符成对关系维护，之后遍历字符串，有以下几种情况：

  1. 当前字符在Map中有对应的值，说明当前字符是起始字符，为(、 [、 {，我们将对应的结束字符放入到Stack中
  2. 当前字符在Map中没有对应的值，说明当前字符是结束字符，为)、 ]、 }，那么栈中应该存放有对应的起始字符，我们将栈中字符出栈，看出栈的字符是否和当前字符一样：
    1. 如果一样，说明括号是成对的，进行下一次循环
    2. 如果不一样，说明括号不是成对的，那么直接返回false
  3. 遍历完字符串后，看看栈中是否还有字符，如果还有字符，那么说明没有匹配完，返回false，如果栈中没有字符了，说明匹配结束，返回true

代码

var isValid = function(s) {

    if (s.length % 2 === 1) return false  //如果字符串字符数为奇数，那么括号不可能成对，直接返回false
    
    const stack = [] //创建Stack

    const charMap = {  //创建成对括号关系Map
        "(": ")",
        "{": "}",
        "[": "]"
    }

    for (let i = 0; i < s.length; i++) {
        const currentChar = s[i]
        if (charMap[currentChar]) {  //如果Map中有当前字符的值，说明当前字符为 (、 { 、[
            stack.push(charMap[currentChar]) //将其对应的结束字符存入Stack中
        }else {  //如果Map中不存在当前字符的值，说明当前字符为 )、 }、 ]
            if (stack.pop() !== currentChar) { //将栈中的结束字符出栈，如果这个结束字符不是当前字符的结束字符的话，说明匹配不上，返回false
                return false
            }
        }
    }

    return stack.length === 0 //如果所有的字符都遍历结束，但是栈中还有字符的话，说明字符没有成对匹配完
};