EasyBlind75StringStack

Valid Parentheses

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

Examples

Input
s = '()'
Output
true

Single pair of parentheses.

Input
s = '()[]{}'
Output
true

All brackets are matched correctly.

Input
s = '(]'
Output
false

'(' is matched with ']' which is invalid.

Constraints

  • •1 <= s.length <= 10^4
  • •s consists of parentheses only '()'[]{}'.

Approaches

Repeatedly replace matching pairs until no more can be found.

CodeT: O(n^2) | S: O(n)
def is_valid(s):
    while '()' in s or '[]' in s or '{}' in s:
        s = s.replace('()', '').replace('[]', '').replace('{}', '')
    return len(s) == 0

Use a stack to push opening brackets and pop when a matching closing bracket is found.

CodeT: O(n) | S: O(n)
def is_valid(s):
    stack = []
    mapping = {')': '(', ']': '[', '}': '{'}
    for char in s:
        if char in mapping:
            if not stack or stack[-1] != mapping[char]:
                return False
            stack.pop()
        else:
            stack.append(char)
    return len(stack) == 0

Same stack approach with early termination on odd length.

Diagram

s = '()[]{}' '(' -> stack=['('] ')' -> matches '(' -> stack=[] '[' -> stack=['['] ']' -> matches '[' -> stack=[] '{' -> stack=['{'] '}' -> matches '{' -> stack=[] stack empty -> True
CodeT: O(n) | S: O(n)
def is_valid(s):
    if len(s) % 2 != 0:
        return False
    stack = []
    pairs = {'(': ')', '[': ']', '{': '}'}
    for char in s:
        if char in pairs:
            stack.append(char)
        elif not stack or pairs[stack.pop()] != char:
            return False
    return not stack

Complexity Comparison

Iterative Replacement
T: O(n^2)S: O(n)

Repeatedly replace matching pairs until no more can be found.

Stack
T: O(n)S: O(n)

Use a stack to push opening brackets and pop when a matching closing bracket is found.

Stack with Early Termination
T: O(n)S: O(n)

Same stack approach with early termination on odd length.

Common Mistakes

Forgetting to check if the stack is empty before popping

Not handling the case where the stack is non-empty at the end

Using the wrong mapping direction (should map closing to opening)

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems