2. 有效的括号

题目连接:有效的括号

给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。

  2. 左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1:

输入: "()" 输出: true

示例 2:

输入: "()[]{}" 输出: true

示例 3:

输入: "(]" 输出: false

示例 4:

输入: "([)]" 输出: false

示例 5:

输入: "{[]}" 输出: true

解题思路

给定一段只包括 '(',')','{','}','[',']' 的字符串中,出现了一次左侧括号,那么下一次出现的右侧括号如果是与之对应的,输出 true,否则输出 false。字符串是空时,也要输出 true

  1. 使用一个 map 保存括号的对应关系。

  2. 创建一个容器用于保存字符串中的左侧括号。

  3. 遍历字符串,每遇到一个左侧括号,就将该括号放入容器中。

  4. 如果遇到的符号是右侧括号,则判断容器A中最后一次添加的左侧括号,是否是与之对应的: 如果是,则从容器中移除最后一次添加的左侧括号,然后继续执行; 如果不是,则直接返回 false

  5. 遍历结束后,如果容器中数据的个数为 0,那么返回 true 。有两种情况会得到 true 。 1. 因为如果给定字符串长度为 0,则容器中数据的个数为 0,那么应该输出 true 。 2. 左右括号为成对出现,最后容器中的数据全被移除了,也应该输出 true

代码

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: 有效的括号

Date: 2019.11.09

Author: zhangpeng

Github: https://github.com/fullstack-zhangpeng