@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.
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)
--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:
- Open brackets must be closed with the same type of bracket.
- 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
--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