有效的括号

题目描述

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

有效字符串需满足：

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

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

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

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

示例 4： 输入：s = ”([])“
输出：true

思路&js代码

1、栈

var isValid = function(s) {
    if (s.length % 2) { // s 长度必须是偶数
        return false;
    }
    const mp = {')': '(', ']': '[', '}': '{'};
    const st = [];
    for (const c of s) {
        if (!mp.hasOwnProperty(c)) { // c 是左括号
            st.push(c); // 入栈
        } else if (st.length === 0 || st.pop() !== mp[c]) { // c 是右括号
            return false; // 没有左括号，或者左括号类型不对
        }
    }
    return st.length === 0; // 所有左括号必须匹配完毕
};