20-有效的括号.md

20. 有效的括号

leecode原题

题目

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

有效字符串需满足：

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

示例

示例 1:

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

示例 2:

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

示例 3:

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

示例 4:

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

示例 5:

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

提示：

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

解题思路

思路

该题是一个很典型的使用栈解决问题的经典题目。

具体思路就是:

遍历字符串:

• 情况1: 遇到左括号，直接将左括号对应的右括号入栈
• 情况2: 栈非空, 且右括号和栈顶元素相等，则弹出栈顶元素
• 其他情况: 代表不匹配(比如遇到右括号，但是栈非空，或者右括号和栈顶元素不相同)

遍历完成之后, 栈不为空的话(比如最后都是连续的几个左括号)，则也代表不匹配。

实现

源码

func isValid(s string) bool {
	n := len(s)
	if n == 0 {
		return true
	}
	stack := []byte{} // 用数组实现一个栈
	// 字符括号映射表
	charMap := map[byte]byte{
		'{': '}',
		'(': ')',
		'[': ']',
	}
	for i := 0; i < n; i++ {
		// 如果是左括号，则直接将其对应的右括号入栈
		if s[i] == '{' || s[i] == '(' || s[i] == '[' {
			stack = append(stack, charMap[s[i]])
		} else if len(stack) > 0 && s[i] == stack[len(stack)-1] {
			// 当前字符映射匹配到栈首元素, 栈弹出
			stack = stack[:len(stack)-1]
		} else {
			return false
		}
	}
	// 最终判断栈是否为空
	if len(stack) != 0 {
		return false
	}
	return true
}