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)

  1. 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)

Recommended Posts

I tried LeetCode every day 20. Valid Parentheses (Python, Go)
I tried LeetCode every day 125. Valid Palindrome (Python, Go)
I tried LeetCode every day 136. Single Number (Python, Go)
I tried LeetCode every day 118. Pascal's Triangle (Python, Go)
I tried LeetCode every day 155. Min Stack (Python, Go)
I tried LeetCode every day 9. Palindrome Number (Python, Go)
I tried LeetCode every day 1. Two Sum (Python, Go)
I tried LeetCode every day 141. Linked List Cycle (Python, Go)
I tried LeetCode every day 110. Balanced Binary Tree (Python, Go)
I tried LeetCode every day 14.Longest Common Prefix (Python, Go)
I tried LeetCode every day 119. Pascal's Triangle II (Python, Go)
I tried LeetCode every day 168. Excel Sheet Column Title (Python, Go)
I tried LeetCode every day 111. Minimum Depth of Binary Tree (Python, Go)
I tried LeetCode every day 26. Remove Duplicates from Sorted Array (Python, Go)
I tried LeetCode every day 160. Intersection of Two Linked Lists (Python, Go)
I tried LeetCode every day 108. Convert Sorted Array to Binary Search Tree (Python, Go)
I tried LeetCode every day 167. Two Sum II --Input array is sorted (Python, Go)
I tried LeetCode every day 122. Best Time to Buy and Sell Stock II (Python, Go)
I tried Grumpy (Go running Python).
I tried running faiss with python, Go, Rust
I tried Python> decorator
I tried fp-growth with python
I tried scraping with Python
I tried Python C extension
[Python] I tried using OpenPose
I tried gRPC with Python
I tried scraping with python
I tried to touch Python (installation)
I tried web scraping with python.
I tried using Thonny (Python / IDE)
I tried running prolog with python 3.8.2.
I tried Line notification in Python
I tried SMTP communication with Python
[Python] I tried using YOLO v3
I tried to summarize Python exception handling
I tried to implement PLSA in Python
I tried to implement permutation in Python
I tried scraping Yahoo News with Python
I tried to implement PLSA in Python 2
Python3 standard input I tried to summarize
I tried sending an email with python.
I tried using Bayesian Optimization in Python
I tried non-photorealistic rendering with Python + opencv
I tried using UnityCloudBuild API from Python
I tried to implement ADALINE in Python
I tried a functional language with Python
I tried recursion with Python ② (Fibonacci sequence)
I tried to implement PPO in Python
Python: I tried the traveling salesman problem
Wrangle x Python book I tried it [1]
Mayungo's Python Learning Episode 8: I tried input
[Python] I tried to calculate TF-IDF steadily
I tried scraping Yahoo weather (Python edition)
I tried to touch Python (basic syntax)
I tried the Python Tornado Testing Framework
#I tried something like Vlookup with Python # 2
[LIVE] I tried to deliver the sunrise and sunset times nationwide every day
Python day 1
[Baseball Hack] I tried copying the Python MLB score & grade data acquisition script with Go in half a day
Let Code Day58 Starting from Zero "20. Valid Parentheses"
[Python / DynamoDB / boto3] List of operations I tried