Valid Parentheses

Stack
Easy

Approach

Diagrams

Analysis

Time

O(n)

Space

O(n)
class Solution:
    def isValid(self, string):
        stack = []

        openBrackets = '({['
        closedBrackets = ')}]'

        MAP = {
            ')': '(',
            '}': '{',
            ']': '['
        }

        for bracket in string:
            if bracket in openBrackets:
                stack.append(bracket)
                continue

            correctOrder = len(stack) > 0

            if not correctOrder:
                return False

            lastOpenBracket = stack[-1]
            expectedOpenBracket = MAP[bracket]

            sameType = lastOpenBracket == expectedOpenBracket

            if not sameType:
                return False

            else:
                stack.pop()

        allSameTypeAndCorrectOrder = len(stack) == 0

        return allSameTypeAndCorrectOrder

Learn

#Stack

Videos