有效的括号

题目

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

有效字符串需满足：

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

注意空字符串可被认为是有效字符串。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

示例 1:

输入: "()"
输出: true
示例 2:

输入: "()[]{}"
输出: true
示例 3:

输入: "(]"
输出: false
示例 4:

输入: "([)]"
输出: false
示例 5:

输入: "{[]}"
输出: true

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/valid-parentheses

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解答

思路

这一题参考后缀表达式求值中对括号的处理

  • 遇到左括号：入栈
  • 遇到右括号：判断和栈顶括号是否匹配
    • 匹配就出栈继续往后判断
    • 不匹配就返回错误

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

func isValid(s string) bool {
	if len(s) == 0 {
		return true
	}

	m := map[byte]byte{
		')': '(',
		']': '[',
		'}': '{',
	}
	stk := make([]byte, 0)
	for _, v := range s {
		switch v {
		case '(', '[', '{':
			//  入栈
			stk = append(stk, byte(v))
		default:
			l := len(stk)
			// 匹配不成功：栈空且遇到翻括号 || 和栈顶不匹配
			if l == 0 || stk[l-1] != m[byte(v)] {
				return false
			}
			// 匹配成功，出栈
			stk = stk[:l-1]
		}
	}
	return len(stk) == 0
}

// 执行用时 :0 ms, 在所有 Go 提交中击败了100%的用户
// 内存消耗 :2 MB, 在所有 Go 提交中击败了86.48%的用户

优化

无