20.有效的括号
题目
给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
解题思路
给定一段只包括 '(',')','{','}','[',']'
的字符串中,出现了一次左侧括号,那么下一次出现的右侧括号如果是与之对应的,输出 true
,否则输出 false
。字符串是空时,也要输出 true
。
-
使用一个
map
保存括号的对应关系。 -
创建一个容器用于保存字符串中的左侧括号。
-
遍历字符串,每遇到一个左侧括号,就将该括号放入容器中。
-
如果遇到的符号是右侧括号,则判断容器A中最后一次添加的左侧括号,是否是与之对应的:
如果是,则从容器中移除最后一次添加的左侧括号,然后继续执行;
如果不是,则直接返回false
。 -
遍历结束后,如果容器中数据的个数为 0,那么返回
true
。有两种情况会得到true
。- 因为如果给定字符串长度为 0,则容器中数据的个数为 0,那么应该输出
true
。 - 左右括号为成对出现,最后容器中的数据全被移除了,也应该输出
true
。
- 因为如果给定字符串长度为 0,则容器中数据的个数为 0,那么应该输出
代码
package main
import "fmt"
func main() {
fmt.Println(isValid("()"))
}
func isValid(s string) bool {
symbolMap := map[string]string {
"(": ")",
"[": "]",
"{": "}",
}
stack := NewStack()
for _, val := range s {
character := string(val)
if rightSymbol := symbolMap[character]; rightSymbol != "" {
stack.Push(character)
} else if symbolMap[stack.Pop()] != character {
return false
}
}
return 0 == stack.Length()
}
type Stack struct {
data []string
}
func NewStack() *Stack {
return &Stack{}
}
func (s *Stack) Push(item string) {
s.data = append(s.data, item)
}
func (s *Stack) Pop() string {
if s.Length() == 0 {
return ""
} else {
lastCharacter := s.data[s.Length()-1]
s.data = s.data[0:s.Length()-1]
return lastCharacter
}
}
func (s *Stack) Length () int {
return len(s.data)
}
Title: 20.有效的括号
Date: 2019.11.09
Author: zhangpeng
网友评论