首页 > itarticle > 20 valid parentheses

20 valid parentheses

admin 11月 14, 2020 0

AC and Best Solution

def (self, s):
    """
    :type s: str
    :rtype: bool
    """
    def match(a,b):
        if a == "(" and b == ")":
            return True
        if a == "[" and b == "]":
            return True
        if a == "{" and b == "}":
            return True
        return False
    stack = []
    for i in s:
        if i == "(" or i == "[" or i == "{":
            stack.append(i)
        else:
            if len(stack) > 0 and match(stack[-1],i):
                stack.pop()
            else:
                return False
    return stack == []

Time complexity: O(n)
Space Complexity: O(2)

if element in i is left bracket, push it
else return False if it not match last left bracket