LC-0020 Easy LeetCode

20. Valid Parentheses

Read the full problem statement on LeetCode.

Difficulty: easy Acceptance: 42% Topics: String, Stack

Reading material

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(n)

class Solution(object):
    # @return a boolean
    def isValid(self, s):
        stack, lookup = [], {"(": ")", "{": "}", "[": "]"}
        for parenthese in s:
            if parenthese in lookup:
                stack.append(parenthese)
            elif len(stack) == 0 or lookup[stack.pop()] != parenthese:
                return False
        return len(stack) == 0

Solution from kamyu104/LeetCode-Solutions · MIT