Valid Parentheses

Problem

https://leetcode.com/problems/valid-parentheses/

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.

2. Open brackets must be closed in the correct order.

3. Every close bracket has a corresponding open bracket of the same type.

Example 1:

Input: s = “()”

Output: true

Example 2:

Input: s = “()[]{}”

Output: true

Example 3:

Input: s = “(]”

Output: false

Example 4:

Input: s = “([])”

Output: true

Example 5:

Input: s = “([)]”

Output: false

Constraints:

• 1 <= s.length <= 10:sup:`4`

• s consists of parentheses only '()[]{}'.

Pattern

String, Stack

Approaches

Stack

Explanation

This is a classic use case for stacks. For each opening parenthesis, push it onto the stack. For each closing parenthesis, pop the stack and check if the popped parenthesis belongs with the closing parenthesis. If it doesn’t, return False. At the end, the stack should be empty for the string to be valid.

Code

from collections import deque


def isValid(s: str) -> bool:
    """Checks if a string of parentheses is valid."""
    stack = deque()
    for char in s:
        if char in "({[":
            stack.append(char)
        else:
            if len(stack) == 0:
                return False
            opening = stack.pop()
            if not parentheses_match(opening, char):
                return False

    return len(stack) == 0


def parentheses_match(opening, closing):
    """Checks if a pair of opening and closing parentheses match."""
    return (
        (opening == "(" and closing == ")")
        or (opening == "{" and closing == "}")
        or (opening == "[" and closing == "]")
    )

Test

>>> from valid_parentheses__stack import isValid
>>> isValid('()')
True
>>> isValid('()[]{}')
True
>>> isValid('(]')
False

Complexity

\(n\) is the length of s.

Measure	Complexity	Notes
Time	\(O(n)\)	single pass through s.
Auxiliary Space	\(O(n)\)	stack

valid_parentheses__stack.isValid(s: str) → bool

Checks if a string of parentheses is valid.

valid_parentheses__stack.parentheses_match(opening, closing)

Checks if a pair of opening and closing parentheses match.