Skip to main content

#20. Valid Parentheses | LeetCode Python Solution

Problem​

LeetCode Problem

  1. Valid Parentheses

Python Solution​

Use Python list data structure to simulate stack and check if a given string has valid parentheses.

class Solution:
    def isValid(self, s: str) -> bool:
        """
        Drawing and tests
        https://excalidraw.com/#json=XfbKWwgJNY6-maTsEnF6g,UV3CBg7bPcsH8mBqW74iqQ
        """

        # Not valid if we have odd number of parentheses
        if len(s) % 2 == 1:
            return False

        # Loop through each character in the string
        stack = []
        for ch in s:
            # Always push the first parenthesis to the stack
            if len(stack) == 0:
                stack.append(ch)
            else:
                # Pop the top item off the stack and compare with the current chracter to check if they are the same bracket type
                topStackItem = stack.pop(len(stack) - 1)
                if not (
                    (ch == ")" and topStackItem == "(")
                    or (ch == "]" and topStackItem == "[")
                    or (ch == "}" and topStackItem == "{")
                ):
                    # Push them back to the stack if they are NOT of the same bracket type
                    stack.append(topStackItem)
                    stack.append(ch)

        # Valid if we end up with an empty stack
        if len(stack) == 0:
            return True
        else:
            return False