有效的括号
LeetCode20. 有效的括号
题目描述
给定一个只包括 (
,)
,{
,}
,[
,]
的字符串 s
,判断字符串是否有效。
有效字符串需满足:
-
左括号必须用相同类型的右括号闭合。
-
左括号必须以正确的顺序闭合。
示例 1:
示例 2:
1
2
|
输入:s = "()[]{}"
输出:true
|
示例 3:
示例 4:
1
2
|
输入:s = "([)]"
输出:false
|
示例 5:
1
2
|
输入:s = "{[]}"
输出:true
|
提示:
1 <= s.length <= 10^4
- s 仅由括号
()[]{}
组成
思路
题目要求:
- 给定一个只包括括号的字符串,判断字符串中的括号是否匹配
- 返回判断结果
由于栈结构的特殊性,非常适合做对称匹配类的题目。
首先要弄清楚,字符串里的括号不匹配有几种情况。
- 第一种情况,字符串里左方向的括号多余了 ,所以不匹配。
- 第二种情况,括号没有多余,但是括号的类型没有匹配上。
- 第三种情况,字符串里右方向的括号多余了,所以不匹配。
代码
Go
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
32
33
|
func isValid(s string) bool {
// 用字典事先存好括号的匹配规则
hashmap := map[byte]byte{
')': '(',
'}': '{',
']': '[',
}
// 用切片模拟栈
stack := make([]byte, 0)
if s == "" {
// 空串有效
return true
}
// 遍历字符串
for i := 0; i < len(s); i++ {
if s[i] == '(' || s[i] == '{' || s[i] == '[' {
// 遍历字符串时遇到左括号 压栈
stack = append(stack, s[i])
} else if len(stack) != 0 && stack[len(stack)-1] == hashmap[s[i]] {
// 遍历字符串时遇到右括号 栈非空且栈顶元素与该右括号匹配 弹栈
stack = stack[:len(stack)-1]
} else {
// 遍历字符串时遇到左括号 栈为空或栈顶元素与该右括号不匹配 证明有右括号多余
return false
}
}
if len(stack) != 0 {
// 遍历完了字符串,但是栈非空,证明有左括号多余
return false
} else {
return true
}
}
|
Link
GitHub