题目描述#

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

有效字符串需要满足三个条件：左括号必须用相同类型的右括号闭合，左括号必须按照正确顺序闭合，并且每个右括号都要有对应的左括号。

思路#

这道题的核心是用栈维护“当前还没有匹配完成的括号”。

遍历字符串时，遇到左括号就把它对应的右括号压入栈中。比如遇到 (，就把 ) 放进栈里；遇到 [，就把 ] 放进去。这样做的好处是，后面一旦读到右括号，只需要判断它是否等于当前栈顶即可，不需要再额外反查左括号和右括号的配对关系。

这份代码先判断字符串长度是否为奇数。如果长度是奇数，括号不可能两两配对，可以直接返回 false。在遍历过程中，如果当前字符是左括号，就把期望出现的右括号压栈；如果当前字符是右括号，就检查栈是否为空，以及它是否和栈顶字符一致。只要其中一个条件不满足，就说明括号类型不对，或者闭合顺序不对。

最后还要判断栈是否为空。如果遍历结束后栈里还有元素，说明还有左括号没有匹配完成，因此结果也应该是 false。

这个做法的时间复杂度是 O(n)，空间复杂度是 O(n)。

代码#

func isValid(s string) bool {
	stack := []byte{}
	mp := map[byte]byte{
		'(': ')',
		'[': ']',
		'{': '}',
	}
	if len(s)%2 == 1 {
		return false
	}
	for i := 0; i < len(s); i++ {
		if v, ok := mp[s[i]]; ok {
			stack = append(stack, v)
		} else {
			if len(stack) == 0 || stack[len(stack)-1] != s[i] {
				return false
			}
			stack = stack[:len(stack)-1]
		}
	}
	return len(stack) == 0
}