#20

Easy

auto_awesomeStack-based bracket matching

LeetCode Problem Workspace

Valid Parentheses

Determine if a string of parentheses, brackets, and braces is correctly nested using a stack for proper order validation.

stack string

Problem Statement

Given a string containing only parentheses '()', square brackets '[]', and curly braces '{}', determine whether the string is valid. A valid string requires every opening bracket to be closed by the same type of bracket, and brackets must close in the correct order. Simply counting bracket occurrences is insufficient because order and nesting define validity.

For example, '()[]{}' is valid because each opening bracket has a matching closing bracket in proper order. Conversely, '([)]' is invalid because the closing order violates nesting rules: ')' closes '(' prematurely while '[' is still unmatched. Your task is to implement a function that efficiently verifies this validity for strings up to length 10,000.

Examples

Example 1

Input: s = "()[]{}"

Output: true

Each opening bracket is closed by the right type, and every pair is closed in the correct order.

Example 2

Input: s = "([)]"

Output: false

The counts look balanced, but the order is wrong. ')' tries to close '(' while '[' is still the most recent unmatched opening bracket.

Constraints

1 <= s.length <= 10^4
s consists only of parentheses, square brackets, and curly braces.
A valid answer depends on both bracket type and nesting order, not just counts.
Returning early on the first mismatch is allowed and usually clearer.

Solution Approach

Stack Iteration Method

Iterate through the string and push every opening bracket onto a stack. For each closing bracket, check if the stack is non-empty and if the top element matches the closing bracket type. If it matches, pop the top element; otherwise, return false immediately. This approach ensures that nesting order is preserved and early mismatches are detected efficiently, reflecting the stack-based bracket matching pattern central to this problem.

Hash Map for Matching Brackets

Use a hash map to store bracket pairs: {')':'(', ']':'[', '}':'{'}. When a closing bracket is encountered, look up the expected opening bracket and compare it with the top of the stack. This avoids multiple conditional checks and guarantees correct type matching. The stack still enforces order, while the hash map simplifies comparisons, preventing subtle mistakes where counts might appear correct but the order is wrong.

Early Exit Optimization

Immediately return false when a closing bracket does not match the stack's top element or if the stack is empty. This avoids unnecessary iteration over the rest of the string and is particularly useful for large inputs or deeply nested mismatches. This optimization leverages the failure mode of bracket order violation, ensuring fast detection of invalid sequences without scanning the full input unnecessarily.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

The time complexity is O(n) because each character is processed once, with pushes and pops on the stack taking constant time. The space complexity is O(n) in the worst case, storing all opening brackets when no early mismatches occur. These bounds reflect the stack-based approach, where both iteration and auxiliary storage grow linearly with input length.

What Interviewers Usually Probe

Do you handle mismatched closing brackets without scanning the entire string?
Can you explain why using counts alone does not guarantee validity in nested brackets?
Will you implement a stack-based approach to maintain proper bracket order?

Common Pitfalls or Variants

Common pitfalls

Relying only on counts of brackets, which ignores nesting order and can produce false positives.
Not checking if the stack is empty before popping, causing runtime errors for strings starting with closing brackets.
Failing to return early on mismatch, unnecessarily iterating over the remainder and reducing efficiency.

Follow-up variants

Longest Valid Parentheses: Compute the length of the longest well-formed parentheses substring.
Remove Invalid Parentheses: Generate all valid strings by removing the minimum number of invalid brackets.
Minimum Add to Make Parentheses Valid: Determine how many brackets must be added to balance a string.

FAQ

What does 'Valid Parentheses' mean in this problem?

A string is valid if every opening bracket has a matching closing bracket of the same type and all brackets are properly nested in order.

Why do I need a stack for this problem?

The stack enforces the correct nesting order by keeping track of unmatched opening brackets, which counts alone cannot guarantee.

Can I solve this problem using only counters for each bracket type?

No, using only counts fails when brackets are nested improperly, as a closing bracket may match the count but violate order, producing incorrect results.

What should I do if the string starts with a closing bracket?

Immediately return false because a closing bracket without a preceding matching opening bracket violates the stack-based order, signaling an invalid string.

How can I optimize checking large bracket strings?

Return early on the first mismatch and use a hash map to match bracket types, reducing unnecessary iterations while maintaining O(n) complexity.

terminal

Solution

Solution 1: Stack

Traverse the bracket string $s$. When encountering a left bracket, push the current left bracket into the stack; when encountering a right bracket, pop the top element of the stack (if the stack is empty, directly return `false`), and judge whether it matches. If it does not match, directly return `false`.

class Solution:
    def isValid(self, s: str) -> bool:
        stk = []
        d = {'()', '[]', '{}'}
        for c in s:
            if c in '({[':
                stk.append(c)
            elif not stk or stk.pop() + c not in d:
                return False
        return not stk

Continue Practicing

#1 two sum