LeetCode No.20 [Valid Parentheses]

Description

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.

Leet Code Link


遍历数组实现

遍历字符串数组,如果遇到左括号部分则将起添加到列表中,如果遇到右括号部分则判断列表结尾的括号是否对应:

  • 如果对应则舍弃列表结尾字符并继续遍历
  • 如果不对应则返回false

其中列表可以使用List或者数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func isValid(s string) bool {
symbolList := list.New()
symbolMap := map[byte]byte{')': '(', ']': '[', '}': '{'}
for i := 0; i < len(s); i++ {
val := s[i]
switch val {
case '[', '{', '(':
symbolList.PushBack(val)
case ']', '}', ')':
if symbolList.Len() == 0 {
return false
}
last := symbolList.Back()
if last.Value != symbolMap[val] {
return false
}
symbolList.Remove(last)
}
}
return symbolList.Len() == 0
}