大家好，我是木川
一、题目描述
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = "()"
输出：true示例 2：
输入：s = "()[]{}"
输出：true示例 3：
输入：s = "(]"
输出：false提示：
1 <= s.length <= 104s仅由括号'()[]{}'组成
二、题解
一）栈 + 哈希表
思路：使用栈进行字符串的入栈和出栈，使用哈希表存储右括号对应的左括号
1、遍历字符串，碰到左括号入栈
2、遍历字符串，碰到右括号出栈，并且判断栈顶的左括号和当前右括号是否是一对
代码：
func isValid(s string) bool {
stack := []byte{}
pairs := map[byte]byte{
')': '(',
']': '[',
'}': '{',
}
for i := 0; i < len(s); i++ {
if _, ok := pairs[s[i]]; !ok {
// 入栈：（、[、{
stack = append(stack, s[i])
} else {
// 碰到 )、]、} 但栈为空
if len(stack) == 0 {
return false
}
// 出栈：)、]、}
if stack[len(stack)-1] != pairs[s[i]] {
return false
}
stack = stack[:len(stack)-1]
}
}
return len(stack) == 0
}时间复杂度：O(n)，一次 for 循环遍历 O(n)
空间复杂度：O(n)，栈使用的空间为 O(n)，而哈希表使用的空间为 O(6)
今天的分享就到这里了，加下面微信拉你进编程技术交流群
如果对你有帮助，帮我点一下在看或转发，欢迎关注我的公众号
