leetcode 20 (opens new window)

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

有效字符串需满足：

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

示例 1：

输入：s = "()"
输出：true

示例 2：

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

示例 3：

输入：s = "(]"
输出：false

示例 4：

输入：s = "([)]"
输出：false

示例 5：

输入：s = "{[]}"
输出：true

提示：

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

解答:

使用栈结构来解题，当有左括号时进行入栈操作，当有右括号时进行出栈操作，当循环结束后栈的长度为空，则认为有效；

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    let stack = [];
    let map = { // map结构存储反括号
        ")": "(",
        "]": "[",
        "}": "{"
    };
    if(map[s.charAt(0)]) return false; //如果首位不是左括号返回false
    for(let str of s.split('')) {
        if(!map[str]) { // 如果为左括号则入栈
            stack.push(str);
        }else { 
            if(stack[stack.length - 1] === map[str]) { // 否则判断栈顶元素是否与下个字符对应，是则出栈
                stack.pop();
            }else { //否则直接return false
                return false;
            }
        }
    }
    return !stack.length; // 当栈全为空，说明字符有效
};