有效的括号

问题

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

有效字符串需满足：

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

示例 1：

输入： s = ”()” **输出：**true

示例 2：

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

示例 3：

输入： s = ”(]” **输出：**false

提示：

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

方法一

解题思路

遍历字符串，如果遇到{、[、( 就进行压栈，否则就进行出栈，并比对是否闭合，不闭合直接返回 false 。最后栈为空，则为有效括号。

let isValid = function(s) {
    let stack = [], length = s.length;
    if(length % 2) return false;
    for(let item of s){
        switch(item){
            case "{":
            case "[":
            case "(":
                stack.push(item);
                break;
            case "}":
                if(stack.pop() !== "{") return false;
                break;
            case "]":
                if(stack.pop() !== "[") return false;
                break;
            case ")":
                if(stack.pop() !== "(") return false;
                break;
        }
    }
    return !stack.length;
};

下面使用Map来存储一对括号。

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    const n = s.length
    // 不是偶数
    if (n % 2 === 1) {
        return false
    }
    let stack = []
    let pairs = new Map([
        [')', '('],
        [']', '['],
        ['}', '{']
    ])
    s.split('').forEach(ch => {
        if (pairs.has(ch)) {
            // 出栈并比较
            if (!stack.length || stack[stack.length - 1] != pairs.get(ch)) return false
            stack.pop()
        } else {
            // 压栈
            stack.push(ch)
        }
    })
    return !stack.length
}