This article is participating in Python Theme Month. See the link to the event for more details

describe

Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.

An input string is valid if:

  • Open brackets must be closed by the same type of brackets.
  • Open brackets must be closed in the correct order.

Example 1:

Input: s = "()"
Output: true
Copy the code

Example 2:

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

Example 3:

Input: s = "(]"
Output: false
Copy the code

Example 4:

Input: s = "([)]"
Output: false
Copy the code

Example 5:

Input: s = "{[]}"
Output: true
Copy the code

Note:

1 <= s.length <= 10^4
s consists of parentheses only '()[]{}'.
Copy the code

parsing

According to the meaning of the question, is to determine whether the given three kinds of parenthesis symbols of the string is suitable for the method, the provision of the legal parenthesis string must meet two points:

  • The opening parenthesis must correspond to the closing parenthesis of the same type
  • The opening brackets must be closed in the correct order

“()[]{}”; ()[]{}; In addition, different parentheses cannot be nested illegally, such as “([)]”; Instead, it is nested within another set of parentheses in the form of full open and close parentheses. Such as “{} []”.

“{[][]{()}()}” is a valid string. You can always replace () or [] or {} with an empty string. If the length of the string has not changed since the replacement, you can simply return False to indicate that the parenthesis string s is illegal. Otherwise, loop through the replacement until s becomes empty and return True to indicate that the symbol string is legal. It’s easier to understand in code.

answer

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        while len(s) > 0:
            t = len(s)
            s = s.replace('()', '')
            s = s.replace('{}', '')
            s = s.replace('[]', '')
            if t == len(s): return False
        return True

        	      
		
Copy the code

The results

Runtime: 10000 ms, faster than 7.62% of Python online submissions for Valid Parentheses. 10000 MB, less than 12.31% of Python online submissions for Valid Parentheses.Copy the code

parsing

The other thing we can do is we can do this with a stack idea, because the parentheses have to correspond, so we can walk through the string s of parentheses, initialize a stack, put the first element in the stack, and walk through the second element, If the element is the parenthesis corresponding to the last element in the stack, then stack.pop() will remove the last element, otherwise append the element to the stack, and the loop will continue this way, returning True if the last result is an empty string indicating that s is valid. Otherwise return False indicating that s is illegal. Combined with the code is easier to understand, of course, can also further simplify the code process, you can think about optimization.

answer

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = [s[0]]
        for c in s[1:]:
            if c == '(' or c == '{' or c == '[':
                stack.append(c)
            elif not stack:
                return False
            elif c == ')' and '(' != stack.pop():
                return False
            elif c == '}' and '{' != stack.pop():
                return False
            elif c == ']' and '[' != stack.pop():
                return False
        return len(stack)==0            	      
		
Copy the code

The results

Runtime: 24 ms, faster than 39.53% of Python online submissions for Valid Parentheses. 10000 MB, less than 59.80% of Python online submissions for Valid Parentheses.Copy the code

Link: leetcode.com/problems/va…

Your support is my greatest motivation