题目描述
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相同类型的左括号。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
思路
使用栈，遍历输入字符串
如果当前字符为左半边括号时，则将其压入栈中
如果遇到右半边括号时，分类讨论：
1）如栈不为空且为对应的左半边括号，则取出栈顶元素，继续循环
2）若此时栈为空，则直接返回 false
3）若不为对应的左半边括号，反之返回 false
关键点解析
-
栈的基本特点和操作
-
可以用数组来模拟栈
比如 入： push 出：pop 就是栈。 入： push 出 shift 就是队列。 但是这种算法实现的队列在头部删除元素的时候时间复杂度比较高，可以参考一下双端队列。
算法流程
如果 c 是左括号，则入栈 push； 否则通过哈希表判断括号对应关系，若 stack 栈顶出栈括号 stack.pop() 与当前遍历括号 c 不对应，则提前返回 false.
复杂度分析
时间复杂度：$O(n)$，其中 nn 是字符串 ss 的长度。
空间复杂度：$O(n+∣Σ∣)$，其中 $Σ$ 表示字符集，本题中字符串只包含 66 种括号，$∣Σ∣=6$。栈中的字符数量为 $O(n)$，而哈希表使用的空间为 $O(∣Σ∣)$，相加即可得到总空间复杂度。
代码
const dict = {
"(": ')',
"[": "]",
"{": "}"
}
var isValid = function (s) {
const stack = []
if (s.length % 2 !== 0) return false // 长度为奇数肯定错误
for (let i = 0; i < s.length; i++) {
if (dict[s[i]]) { // 是开头符号 入栈
stack.push(s[i])
} else {//是结尾符号
if (stack.length === 0) return false
if (dict[stack[stack.length - 1]] === s[i]) { //能合并则出栈
stack.pop()
} else { // 不能合并说明错误
return false
}
}
}
return !stack.length // 栈清空则表示全部合并完成
};