Intuition

Recursive approach won’t work, it’s too expensive.

Approach

Use a stack to keep track of the opening brackets.

Whenever we see a closing bracket, we check if the top of the stack has the corresponding closing one.

When we see a closing bracket we will return False if the stack:

• Does not have any element
• The top of the stack does not match with the closing bracker

After going through all character, if there’s any element left in the stack, we also return False.

The only scenario where we return true is if check all characters and at the end we have a stack with zero elements.

Complexity

• Time complexity: O(n)

• Space complexity: O(n) (we need an extra structure)

Code

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        
        stack = []
        _map = {
            ')':'(',
            ']':'[',
            '}':'{'
        }

        for c in s:
            if c == "(" or c == "[" or c == "{":
                stack.append(c)
            else:
                if len(stack) == 0:
                    return False
                top = stack[-1]
                if _map[c] == top:
                    stack.pop()
                else:
                    return False
        
        return len(stack) == 0