一、题目描述

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

有效字符串需满足：

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

示例1：

输入： s = "()"
输出： true
复制代码

示例2：

输入： s = "()[]{}"
输出： true
复制代码

示例3：

输入： s = "(]"
输出： false
复制代码

示例4：

输入： s = "([)]"
复制代码

示例5：

输入： s = "{[]}"
输出： true
复制代码

提示：

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

二、思路分析

这题是典型的堆栈问题，我们应该使用栈解决这个问题。

1. 首先我们需要借助Map数据结构存储每一对括号。

2. 初始化一个空栈，接着循环字符串，如果遇到左括号，我们则需要该左括号推（push）入栈中。

3. 如果遇到右括号，首先需要判断栈是否为空，以及栈顶元素是否是该右括号对应的左括号（这时候Map数据结构就派上用场了），若栈为空，则说明左右括号数量不一致，返回false。若栈顶元素不为对应括号，说明左右括号不匹配，返回false。

4. 剩下的情况那就肯定匹配正确，我们需要弹出栈顶（pop）元素。

5. 最后返回结果，true or false，我们通过判断栈是否为空即可，若栈为空，则括号有效，反之无效。

三、AC代码

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    let stack = [];
    let map = new Map([
        ["}","{"],
        [")","("],
        ["]","["],
    ])
    for (let str of s) {
        if (!map.has(str)) {
            stack.push(str)
        } else {
            if (!stack.length || stack[stack.length-1] !== map.get(str)) {
                return false
            }
            stack.pop()
        }
    }
    return !stack.length;
};
复制代码

四、总结

这题经常出现在面试中，非常经典，可以很好地考察面试者对栈这种数据结构的掌握程度，因此要熟练掌握这道题的精髓所在。