leetcode - 20. 有效的括号

题目:

1
2
3
4
5
6
7
给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。

有效字符串需满足:

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

解答:

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
// 第一种解法
func isValid(s string) bool {
var tmp []string

arr := strings.Split(s, "")
for _, x := range arr {
c := x
if c == "(" || c == "[" || c == "{" {
tmp = append(tmp, c)
} else {
if len(tmp) == 0 {
return false
}

charTop := tmp[len(tmp)-1]
tmp = append(tmp[:len(tmp)-1], tmp[len(tmp):]...)
if c == ")" && charTop != "(" {
return false
}
if c == "]" && charTop != "[" {
return false
}

if c == "}" && charTop != "{" {
return false
}
}
}

if len(tmp) != 0 {
return false
}

return true
}

// 第二种解法:
func isValid(s string) bool {
var (
tmp []string
True bool = true
)
validMap := map[string]string{
")": "(",
"}": "{",
"]": "[",
}

sArray := strings.Split(s, "")

for _, x := range sArray {
// fmt.Println(x)
if _, ok := validMap[x]; !ok {
tmp = append(tmp, x)
continue
}
if len(tmp) != 0 {
v := tmp[len(tmp)-1]
tmp = append(tmp[:len(tmp)-1], tmp[len(tmp):]...)
if v != validMap[x] {
True = false
break
}
} else {
True = false
break
}
}
if len(tmp) != 0 {
True = false
}

return True
}