“This is the 8th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021”

Brush algorithm, is never to memorize the problem, but to practice the actual problem into a concrete data structure or algorithm model, and then use the corresponding data structure or algorithm model to solve the problem. In my opinion, with this kind of thinking, I can not only solve the interview problems, but also learn to think in daily work. How to abstract the actual scene into the corresponding algorithm model, so as to improve the quality and performance of the code

Valid parentheses

Leetcode-20. Valid parentheses

Topic describes

Given a only include a ‘(‘,’) ‘, ‘{‘,’} ‘, ‘/’, ‘ ‘the string s, determine whether a string is effective.

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

The sample

Example 1

Input: s = "()" output: trueCopy the code

Example 2

Input: s = "()[]{}" Output: trueCopy the code

Example 3

Input: s = "(]" Output: falseCopy the code

Tip:

  • 1 <= s.length <= 104
  • sOnly by brackets'[] {} ()'composition

The problem solving

Train of thought

This can be solved by using the data structure stack. When an open parenthesis is encountered, it is pushed onto the stack, and when a close parenthesis is encountered, the top element of the stack is popped to match the close parenthesis. If it does not match, the requirement is not met, and if it does, traversal continues until the string is traversed and the stack is empty

It’s not hard to imagine that the first character should not be a close parenthesis, because if it is a close parenthesis, it definitely does not satisfy the condition. You can maintain a map that stores matching parentheses, with key as the right parenthesis and value as the left parenthesis

  • If a close parenthesis is encountered, the top of the stack element is fetched for comparison
  • If an open parenthesis is encountered, it is pushed onto the stack

code

func IsValid(s string) bool { n := len(s) if n % 2 ! = 0 { return false } mapBrackets := map[byte]byte{ ')':'(', ']':'[', '}':'{', } stack := []byte{} for i:=0; i < n;  i++ { if _, ok := mapBrackets[s[i]]; ok { if len(stack) == 0 || stack[len(stack)-1] ! = mapBrackets[s[i]] { return false } stack = stack[:len(stack)-1] } else { stack = append(stack, s[i]) } } if len(stack) == 0 { return true } return false }Copy the code