020.有效的括号.md

题目描述

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

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

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

示例

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

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

思路

利用栈对括号进行匹配，下一个如果和栈顶的括号匹配成功则出栈，否则则入栈。当最后为空栈时则全部符合。
匹配的方式可以采用两个字符拼接后和 '()'、'{}'、'[]'匹配，从而避免复杂的匹配对应操作。

代码

/**
 * @param {string} s
 * @return {boolean}
 */
let isValid = function(s) {
    let l = s.length;
    if (l === 0) return true;
    if (l % 2 !== 0) return false;
    let arr = [s[0]];
    for (let i = 1; i < l; i++) {
        let cur = arr[arr.length - 1] + s[i];
        if (cur === '()' || cur === '{}' || cur === '[]') {
            arr.pop();
        }
        else {
            arr.push(s[i])
        }
    }
    return arr.length === 0;
};