-
Notifications
You must be signed in to change notification settings - Fork 0
/
020.go
41 lines (37 loc) · 801 Bytes
/
020.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
34
35
36
37
38
39
40
41
package p020
/**
Given a string containing just the characters '(', ')', '{', '}', '[' and ']',
determine if the input string is valid.
The brackets must close in the correct order, "()" and "()[]{}"
are all valid but "(]" and "([)]" are not.
*/
//use stack
func isValid(s string) bool {
sLen := len(s)
if sLen%2 != 0 {
return false
}
//fmt.Println(s)
hMap := map[byte]byte{')': '(', '}': '{', ']': '['}
stack := make([]byte, sLen/2)
stackLen := 0
for i := 0; i < sLen; i++ {
v, ok := hMap[s[i]]
//fmt.Println(i, stack, stackLen)
if ok {
if stackLen > 0 && stack[stackLen-1] == v {
stackLen--
} else {
return false
}
} else {
if stackLen >= sLen/2 {
return false
} else {
stack[stackLen] = s[i]
stackLen++
}
}
}
return stackLen == 0
}