美文网首页
20.有效的括号

20.有效的括号

作者: zhangPeng丶 | 来源:发表于2019-11-09 13:21 被阅读0次

20.有效的括号

题目

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

有效字符串需满足:

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

Date: 2019.11.09

Author: zhangpeng

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

相关文章

网友评论

      本文标题:20.有效的括号

      本文链接:https://www.haomeiwen.com/subject/ppxnbctx.html