20. Valid Parentheses (Python)

Related Topic

Stack.

Description

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

An empty string is also considered valid.

Sample I/O

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

Methodology

This is a very basic stack question. We will use stack to store unclosed parenthese while iterating the string, once we find a closed parenthese which mean the top element of the stack is matched with the current parenthese, then we pop out the top parenthese and continue. If the final stack is empth that means the string contain valid parentheses

    def isValid(self, s: str) -> bool:
        if not s: return True
        char_map, stack={'(':')','{':'}','[':']'},[]
        for e in s:
            if not stack or stack[-1] not in char_map or char_map[stack[-1]] != e:
                stack.append(e)
            else:
                stack.pop()
        return True if not stack else False

BigO

Iterate the string once will cost total O(n) time