有效的括号

[Bulandent]

有效的括号

难度：简单
来源：20. 有效的括号

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

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

示例 3:

输入: "(]"
输出: false

示例 4:

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

示例 5:

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

思路：

• 括号必须是成对出现的，所以字符串长度一定是偶数；
• 括号必须是成对出现的，这个机制和 Map 这种一一对应的映射关系一致，所以可以用 Map 来映射它们之间的关系；
• 当遍历字符串的时候，如果是左括号（Map 的键）则压入栈中，否则它一定是右括号，则需要用栈最后一位存的 Map 键去取对应的值然后和当前字符匹配，如果匹配则把栈中的最后一位键出栈，否则 返回 false
• 优化：当遍历字符串的时候，如果当前字符是右括号，则说明前面一定出现过左括号即栈中一定压入了数据，所以此时栈的长度不应该为 0；
• 最后，如果一个字符串是括号顺序匹配的，那么栈中不应该存在字符，即所有被压入栈中的左括号都已经因为匹配到了右括号而被出栈，所以此时的栈长度应该为 0；

题解：

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    let l = s.length
    if (l % 2 !== 0) return false

    let stack = []
    let map = new Map([
        ['(', ')'],
        ['[', ']'],
        ['{', '}']
    ])
    for (let i = 0; i < l; i++) {
        if (map.has(s[i])) {
            stack.push(s[i])
        } else {
            if (stack.length === 0) return false
            if (map.get(stack[stack.length - 1]) === s[i]) stack.pop()
            else return false
        }
    }
    return stack.length === 0
};