20. 有效的括号

题目描述：

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

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 1 <= s.length <= 10^4
• s 仅由括号 ’()[]{}’ 组成

---

解题分析及思路：

思路：

解决这个问题，需要保证字符串内的所有字符括号都是成对的，并且每一对的左括号必定出现在右括号的左边。

为保证有序性，可以使用栈来解决这个问题，遍历字符串：

• 如果是左括号就入栈
• 如果是右括号就出栈
• 如果出栈的括号和当前括号不匹配，就返回 false
• 如果遍历完字符串后栈不为空，也返回 false。

可以使用 map 来存储括号的对应关系，这样代码会更简洁。

var m = map[uint8]uint8{
	')': '(',
	'}': '{',
	']': '[',
}

func isValid(s string) bool {
	stack := make([]uint8, 0)
	for index := range s {
		if _, ok := m[s[index]]; !ok {
			stack = append(stack, s[index])
		} else {
			if len(stack) == 0 || stack[len(stack)-1] != m[s[index]] {
				return false
			}
			stack = stack[:len(stack)-1]
		}
	}
	return len(stack) == 0
}

复杂度：

• 时间复杂度：O(N)，其中 N 是 s 的长度。
• 空间复杂度：O(N)，其中 N 是 s 的长度。

执行结果：

• 执行耗时:1 ms,击败了12.88% 的Go用户
• 内存消耗:2 MB,击败了15.79% 的Go用户