The title

Given a string containing only ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘, ‘]’, check whether the string is valid.

A valid string must meet the following requirements:

  1. An open parenthesis must be closed with a close parenthesis of the same type.
  2. The left parentheses must be closed in the correct order.

Note that an empty string can be considered a valid string.

Example 1:

Input:"()"Output:true
Copy the code

Example 2:

Input:"[the] {} ()"Output:true
Copy the code

Example 3:

Input:"(]"Output:false
Copy the code

Example 4:

Input:"([]"Output:false
Copy the code

Example 5:

Input:"{[]}"Output:true
Copy the code

Their thinking

Given a string containing only ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘, ‘]’, if a left parenthesis occurs once, print true if the next right parenthesis occurs, false otherwise. Also print true if the string is empty.

  1. Use a map to hold the parentheses.

  2. Create a container to hold the left parentheses in the string.

  3. Iterating through the string, placing each left parenthesis into the container as it encounters it.

  4. If the symbol encountered is A right parenthesis, determine whether the last left parenthesis added to container A corresponds to it. If so, remove the last left parenthesis added to container A and continue. If not, return false.

  5. At the end of the loop, return true if the number of data in the container is 0. There are two cases where you get true.

    1. Because if given a string length of 0, the number of data in the container is 0, it should printtrue 。
    2. The left and right parentheses appear in pairs, and finally all the data in the container is removed and should be printedtrue 。

code

package main

import "fmt"

func main(a) {
   fmt.Println(isValid("()"))}func isValid(s string) bool {
   symbolMap := map[string]string {
      "(": ")"."[": "]"."{": "}",
   }

   stack := NewStack()
   for _, val := range s {
      character := string(val)
      ifrightSymbol := symbolMap[character]; rightSymbol ! ="" {
         stack.Push(character)
      } else ifsymbolMap[stack.Pop()] ! = character {return false}}return 0 == stack.Length()
}

type Stack struct {
   data []string
}

func NewStack(a) *Stack {
   return &Stack{}
}

func (s *Stack) Push(item string) {
   s.data = append(s.data, item)
}

func (s *Stack) Pop(a) 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 (a) int {
   return len(s.data)
}
Copy the code

Title: 20. Valid parentheses

Date: 2019.11.09

Author: zhangpeng

Making: github.com/fullstack-z…