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