This is the 12th day of my participation in the First Challenge 2022
First, write first
I heard you’re still writing a two-layer for loop to solve the sum of two numbers?
LeetCode 2: Sum of two numbers transfer gate: the median of two sorted arrays, “most” technical solution!
LeetCode 第 3 题 : Longest loop transport gate: Horse-and-cart algorithm to solve longest loop! Manacher
LeetCode 4 题 conversion of string to integer (ATOI) : Solve ATOI with “foolish old man removing mountains” method, think clever!
Continue solving LeetCode, the longest public prefix
One of LeetCode’s “most classic” algorithm problems: the sum of three numbers
LeetCode problem 7: The sum of the nearest three: the sum of the nearest three, wonderful
Question 8: Valid parentheses, for the interview, looking forward to your participation.
Today’s topic
Given a string containing only ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘, ‘]’, check whether the string is valid.
A valid string must meet the following requirements: 1. The left parenthesis must be closed with the same type of the right parenthesis. 2. The left parentheses must be closed in the correct order.
Note that an empty string can be considered a valid string. Example:
Input:"()"Output: true example2Input:"[the] {} ()"Output: true example3Input:"(]"Output: false example4Input:"([]"Output: false example5Input:"{[]}"Output: true,Copy the code
Three, the analysis
This topic was mentioned in Lecture 40 algorithm Interview. When LISTENING to the teacher, I thought of a topic in data Structure in my sophomore year: finding the value of an expression (such as: 5*(3+2)), but it also took two lessons to do this problem with C language, the calculation of the expression is more difficult mainly is the judgment of the operation priority, by contrast, only to judge whether the parentheses are valid, it is too small case.
Fourth, the problem solving
- My approach:
# My way
class Solution:
def isValid(self, s) :
""" :type s: str :rtype: bool """
reg_dict = {') ':'('.'} ':'{'.'] ':'['}
# Bracket matching set
temp_list = []
Temporary storage stack
for i in range(len(s)):
if s[0] in reg_dict:
return False
if s[i] not in reg_dict: # open parenthesis, push
temp_list.append(s[i])
else: # Close parenthesis, take out top of stack, match
if temp_list == []: No open parentheses can match
return False
if not temp_list[-1] == reg_dict[s[i]]: The left and right parentheses do not match
return False
temp_list.pop() The match was successfully removed from the stack
iftemp_list ! = [] :return False
return True
Copy the code
- Submit the results
Test data: 76 groups running time: 20ms beat percentage :100%
Five, doubt
Worthy of mention is that I began to distinguish the characters is left parenthesis or brackets using the list, and then run the results at 76.53%, is also the first mention of the sum of two Numbers do experience, then select the directly use a dictionary, indeed as expected much faster, soared to 100%, this, you can also pay more attention to later, a small details, change your destiny, This is also my first 100%, today a good memory.
Six, the concluding
Ok, last but not least, IT has been more than a month to brush LeetCode. Although I have only brushed 8 questions, I think I have worked hard and learned a lot at the same time.
Now with the brush LeetCode blogger many readers, I dare not to say that I am the best, I can only say that I can do the most attentively, the subject analysis, their thinking, in the search for optimal solution, rather than just send a title to object code, the code is dead, people are living, thought is alive, I will continue to adhere to, at least two questions in a week.
Persistence and hard work: results.
Like to see the message forwarding, four support, the original is not easy. Ok, see you next time, I love the cat love technology, more love si si’s old cousin Da Mian ଘ(˙꒳˙)ଓ Di Di