menu

[LeetCode] 020. Valid Parentheses

Problem (Easy)

020. Valid Parentheses

Given a string 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. Note that an empty string is also considered valid.

Example 1:

  • Input: “()”
  • Output: true

Example 2:

  • Input: “()[]{}”
  • Output: true

Example 3:

  • Input: “(]”
  • Output: false

Example 4:

  • Input: “([)]”
  • Output: false

Example 5:

  • Input: “{[]}”
  • Output: true

Approach 1: Use an Auxilliary Stack

Idea

Use a variable string check to store the current process of the input. Loop the input string, if the looping character is a valid left char, append it to check, if the looping character is a valid right and it’s the correct counterpart of the last element in check, remove the pair from check, else it’s false. If the loop ends succesfully and the length of check not zero, it’s also false, else true.

Solution

class Solution1:
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        dic = {')':'(', ']':'[', '}':'{'}
        check = ''
        for c in s:
            if c in ['(', '[', '{']:
                check += c
            elif c in dic.keys():
                if len(check) == 0:
                    return False
                if check[-1] != dic[c]:
                    return False
                else:
                    check = check[:-1]
        if len(check):
            return False
        else:
            return True

Complexity

  • Time: $O(n)$
  • Space: $O(n)$



KF

Comments