BinarySearch 0036 Balanced Brackets Sequel

Problem statement

https://binarysearch.com/problems/Balanced-Brackets-Sequel/

Solution

Equal to Leetcode 20. Valid Parentheses

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, s):
        dct = {"(": ")", "{": "}", "[": "]"}
        stack = []
        for char in s:
            if char in dct:
                stack.append(char)
            else:
                if not stack or char != dct[stack.pop()]: return False           
        return not stack