Valid Parentheses


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

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. 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

 

Constraints:

  • 1 <= s.length <= 104
  • s consists of parentheses only '()[]{}'.




 class Solution:
    def isValid(self, s: str) -> bool:
        self.stack = []
        opening = {'(': ")", '{': "}", '[':"]"}
        for bracket in s:
            if bracket in opening.keys():
                self.stack.append(bracket)
            else:
                if self.stack:
                    saved = self.stack.pop()
                    if opening[saved] == bracket:
                        continue
                    else:
                        return False
                else:
                    return False

        return len(self.stack) == 0

Random Note


From python 3.7 dict guarantees that order will be kept as they inserted, and popitem will use LIFO order but we need FIFO type system. so we need OrderedDict which have popIten(last = T/F) for this req. One thing, next(iter(dict)) will return the first key of the dict