有效括号

有效的括号

题目描述

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

有效字符串需满足：

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

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

示例

示例1：

输入: "()"
输出: true

示例2：

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

示例3：

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

示例4：

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

思路

• 遍历 s
• 当遇到[, (, { 这些括号的时候就入栈。
• 当遇到], ), } 这些括号的时候就出栈，出栈 判断与当前s[i] 是否匹配为闭合的括号, 即是否是一对。出栈(, 当前s[i]为)则为一对

代码

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    let length = s.length;
    // 做优化，看了答案后添加
    if(length % 2 == 1) {
        return false;
    }

    // 建立字典， 
    let map = {
        "{": "}",
        "(": ")",
        "[": "]",
    }

    let inqueue = ["{", "(", "["];
    let stack = [];

    for(let i = 0; i < s.length; i++) {
        const current = s[i];
        // 判断以下是否属于开合 的括号
        if(inqueue.includes(current)) {
            stack.unshift(current);
            continue;
        }

        // 出栈， 判断当前出栈的括号是否跟 s[i] 为一对，
        let pop = stack.shift();
        if(current !== map[pop]) {
            return false
        } 
    }
    // 最后判断以下栈里面还有没有数据，有的话那就代表还有没有匹配的括号
    return stack.length == 0 ;
};