Problem 20. Valid Parentheses

Description

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.

3. Every close bracket has a corresponding open bracket of the same type.

Solution [Time: O(n), Space: O(n)]

def isValid(self, s: str) -> bool:
        opening = {'(', '{', '['}
        closing = {')', '}', ']'}
        valid = {'()', '{}', '[]'}
        stack = []
        for char in s:
            if char in opening:
                stack.append(char)
            if char in closing:
                if len(stack) == 0:
                    return False 
                bracket = stack.pop()
                if bracket + char not in valid:
                    return False
        return len(stack) == 0

Notes

Found this problem fairly difficult. I required some prompting with a hint to use a stack as I thought this could be done with two pointers somehow.

We use one loop and a stack to store characters so it gives O(n) complexity for both time and space. Not too much more to add to this solution.