Valid Parentheses

Problem

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. A string is valid if every open bracket is closed by the same type of bracket in the correct order.

Approach

Use a stack. Push opening brackets; on a closing bracket, check that the stack top matches. The string is valid iff the stack is empty at the end.

When to Use

Matching/nesting validation — balanced brackets, HTML tags, expression parsing. Any problem where openers must be closed in LIFO order. Keywords: "valid", "balanced", "nested", "well-formed".

Complexity

Time	O(n) -- single pass
Space	O(n) -- stack in worst case (all openers)

Implementation

SolutionTestsChallenge

valid_parentheses

Valid parentheses.

Problem

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. A string is valid if every open bracket is closed by the same type of bracket in the correct order.

Approach

Use a stack. Push opening brackets; on a closing bracket, check that the stack top matches. The string is valid iff the stack is empty at the end.

When to use

Matching/nesting validation — balanced brackets, HTML tags, expression parsing. Any problem where openers must be closed in LIFO order. Keywords: "valid", "balanced", "nested", "well-formed".

Complexity

Time: O(n) -- single pass Space: O(n) -- stack in worst case (all openers)

is_valid

is_valid(s: str) -> bool

Return True if s contains valid matched brackets.

is_valid("()[]{}") True is_valid("(]") False is_valid("([)]") False

Source code in src/algo/stacks_queues/valid_parentheses.py

def is_valid(s: str) -> bool:
    """Return True if *s* contains valid matched brackets.

    >>> is_valid("()[]{}")
    True
    >>> is_valid("(]")
    False
    >>> is_valid("([)]")
    False
    """
    stack: list[str] = []
    match = {")": "(", "]": "[", "}": "{"}

    for ch in s:
        if ch in match:
            if not stack or stack[-1] != match[ch]:
                return False
            stack.pop()
        else:
            stack.append(ch)

    return not stack

tests/stacks_queues/test_valid_parentheses.py

"""Tests for valid parentheses."""

from hypothesis import given
from hypothesis import strategies as st

from algo.stacks_queues.valid_parentheses import is_valid


class TestIsValid:
    def test_simple_valid(self) -> None:
        assert is_valid("()") is True

    def test_multiple_types(self) -> None:
        assert is_valid("()[]{}") is True

    def test_mismatched(self) -> None:
        assert is_valid("(]") is False

    def test_interleaved_invalid(self) -> None:
        assert is_valid("([)]") is False

    def test_nested_valid(self) -> None:
        assert is_valid("{[()]}") is True

    def test_empty_string(self) -> None:
        assert is_valid("") is True

    def test_single_opener(self) -> None:
        assert is_valid("(") is False

    def test_single_closer(self) -> None:
        assert is_valid(")") is False

    @given(
        n=st.integers(min_value=1, max_value=20),
    )
    def test_repeated_pairs_always_valid(self, n: int) -> None:
        """A string of repeated '()' pairs is always valid."""
        assert is_valid("()" * n) is True

    @given(
        n=st.integers(min_value=1, max_value=20),
    )
    def test_nested_parens_always_valid(self, n: int) -> None:
        """Deeply nested parentheses are valid."""
        assert is_valid("(" * n + ")" * n) is True

Implement it yourself

Run: just challenge stacks_queues valid_parentheses

Then implement the functions to make all tests pass. Use just study stacks_queues for watch mode.

Reveal Solution

valid_parentheses

Valid parentheses.

Problem

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. A string is valid if every open bracket is closed by the same type of bracket in the correct order.

Approach

Use a stack. Push opening brackets; on a closing bracket, check that the stack top matches. The string is valid iff the stack is empty at the end.

When to use

Matching/nesting validation — balanced brackets, HTML tags, expression parsing. Any problem where openers must be closed in LIFO order. Keywords: "valid", "balanced", "nested", "well-formed".

Complexity

Time: O(n) -- single pass Space: O(n) -- stack in worst case (all openers)

is_valid

is_valid(s: str) -> bool

Return True if s contains valid matched brackets.

is_valid("()[]{}") True is_valid("(]") False is_valid("([)]") False

Source code in src/algo/stacks_queues/valid_parentheses.py

def is_valid(s: str) -> bool:
    """Return True if *s* contains valid matched brackets.

    >>> is_valid("()[]{}")
    True
    >>> is_valid("(]")
    False
    >>> is_valid("([)]")
    False
    """
    stack: list[str] = []
    match = {")": "(", "]": "[", "}": "{"}

    for ch in s:
        if ch in match:
            if not stack or stack[-1] != match[ch]:
                return False
            stack.pop()
        else:
            stack.append(ch)

    return not stack