Valid Parentheses: Stack matching Pattern

Learning Outcome

After this lesson, you should be able to explain why nested bracket problems need last-in-first-out matching.

Problem Statement

Given a string containing only bracket characters ()[]{}, return true if every opening bracket is closed by the same type of bracket in the correct order.

Brute Force Approach

Repeatedly remove adjacent valid pairs like (), [], and {} until no more pairs can be removed. If the string becomes empty, it is valid.

This proves the nesting idea, but repeated string edits can be slow and clumsy.

Optimized Approach

Push opening brackets onto a stack. When a closing bracket appears, the stack top must be the matching opening bracket. If the stack is empty or the type does not match, return false.

Exact Pseudocode

stack = empty stack
pairs = map closing bracket to opening bracket
for char in s:
  if char is opening bracket:
    push char
  else:
    if stack is empty or stack.top != pairs[char]:
      return false
    pop stack
return stack is empty
  

Reference Code

class Solution:
    def isValid(self, s):
        stack = []
        pairs = {')': '(', ']': '[', '}': '{'}

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

        return len(stack) == 0
  

Sample Dry Run

Complexity

Edge Cases

• Closing bracket appears before any opening bracket.
• Unclosed opening brackets remain at the end.
• Wrong nesting order such as "([)]".

Interview Checklist

• Use stack because the latest opening bracket must close first.
• Check empty stack before reading the top.
• At the end, require the stack to be empty.

FAQs