I tried LeetCode every day 20. Valid Parentheses (Python, Go)

Introduction

@Ishishow is running a free English word site E-tan.

I would like to work on letcode every day to improve my ability as a programmer and give my own way of solving it.

What is Leetcode

leetcode.com This is the practice of coding interviews for software developers. A total of more than 1,500 coding questions have been posted, and it seems that the same questions are often asked in actual interviews.

Introduction to Go language + algorithm I will solve it with Golang and Python to strengthen my brain. (Python is weak but experienced)

6th question (problem 20)

20. Valid Parentheses

--Problem content (Japanese translation)

Think of a string s just contains characters'(', ')', '{', '}', '[' and ']', input Determines if the string is valid.

The input string is valid in the following cases:

1. Open brackets must be closed with the same type of bracket.
2. Open brackets must be closed in the correct order.

Example 1:

  Input: s = "()"
  Output: true

Example 2:

  Input: s = "()[]{}"
  Output: true

Example 3:

  Input: s = "(]"
  Output: false

Example 4:

  Input: s = "([)]"
  Output: false

Example 5:

  Input: s = "{[]}"
  Output: true

Way of thinking

1. Prepare a stack array and a dictionary (map).
2. Enter the corresponding symbol in map
3. Look at the string character by character, add it to the stack if it starts with a parenthesis, and if it's a closing parenthesis, take out the latest one from the stack and check if it matches.

Explanation

1. Define stack and dict (map).
2. dict = {"]":"[", "}":"{", ")":"("}
3. Look at the characters one by one with the for statement.

--Answer code

class Solution:
	def isValid(self, s):
		stack = []
		dict = {"]":"[", "}":"{", ")":"("}
		for char in s:
			if char in dict.values():
				stack.append(char)
			elif char in dict.keys():
				if stack == [] or dict[char] != stack.pop():
					return False
			else:
				return False
		return stack == []

If char in dict.values (): Whether it starts with parentheses

Elif char in dict.keys (): Whether it ends with parentheses

Get the latest stack characters with pop

Assign to stack with append.

--I'll write it in Go too!

  func isValid(s string) bool {
  	stack := make([]rune, 0)
  	m := map[rune]rune{
  		')': '(',
  		']': '[',
  		'}': '{',
  	}
  	for _, c := range s {
  		switch c {
  		case '(', '{', '[':
  			stack = append(stack, c)
  		case ')', '}', ']':
  			if len(stack) == 0 || stack[len(stack)-1] != m[c] {
  				return false
  			}
  			stack = stack[:len(stack)-1]
  		}
  	}
  
  	return len(stack) == 0
  }

This code is a bit tricky, but I got this code to see the strings character by character in Go.

For _, c: = range s loop processing reads the string strings character by character. At that time, c becomes rune type, so map and stack are also defined by rune type.

Since I'm writing Golang, I wrote the process with the switich statement.

--Self memo (Go)

If you look at the strings character by character, rune

Append to slice (ok because it is not fixed length)