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

有效字符串需满足：

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


示例 1：
输入：s = "()"
输出：true

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

示例 3：
输入：s = "(]"
输出：false

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

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


提示：

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

    var isValid = function(s) {
    const len = s.length;
    /**
     * 特殊情况处理
     **/ 

    // 空字符串可被认为是有效字符串
    if(len === 0) {
        return true;
    }

    // 剪枝，字符串长度为奇数，必然无效
    if(len % 2 === 1) {
        return false;
    }

    // 定义字符串匹配 map
    const map = {
        '}' : '{',
        ')' : '(',
        ']' : '['
    }
    // 使用栈来校验闭合情况
    const stack = []
    for (let i = 0; i <= len - 1; i++) {
        if(!map[s[i]]) {
            // 左括号，入栈
            stack.push(s[i]);
        } else {
            // 右括号，出栈，判断如果与前一个括号不匹配，返回 false
            if(map[s[i]] !== stack.pop()) {
                return false;
            } 
        }
        // 剪枝，如果待匹配左括号的数量超过一半，返回 false （奇数已先前排除）
        if(stack.length > len / 2) {
            return false;
        }
    }

    // 遍历结束，如果仍有未匹配完的左括号，返回 false
    if(stack.length > 0) {
        return false;
    } else {
        return true;
    }

}

    image.png