LeetMotion
Given a string containing only (, ), {,}, [, and ], determine if the brackets are valid. Every opening bracket must be closed by the same type of bracket, in the correct order, and every closing bracket must have a corresponding opener.
1 ≤ s.length ≤ 1000[ closes before the inner ( does — wrong order.Brackets must close in reverse order of how they opened — the most recently opened bracket must be the next one to close. That's the exact behavior of a stack: last in, first out.
Walk through the string. When you see an opening bracket, push it. When you see a closing bracket, peek at the stack top — if it's the matching opener, pop it. If it doesn't match (or the stack is empty), the string is invalid. At the end, a valid string leaves an empty stack.
The simplest observation: a valid string must contain at least one adjacent matching pair like (), {}, or []. Repeatedly remove those pairs until nothing can be removed. If the result is an empty string, it was valid.
def isValid(s: str) -> bool:
while '()' in s or '{}' in s or '[]' in s:
s = s.replace('()', '')
s = s.replace('{}', '')
s = s.replace('[]', '')
return s == ''This works, but each pass through the string is O(n) and you may need O(n) passes — so overall O(n²). For s.length = 1000 it's fine, but the stack solution is O(n) and cleaner to reason about.
One pass. One stack. For each character:
False.After the loop, if the stack is empty, every opener was matched. Return True.
closeToOpen map is the trick that keeps the code clean. Instead of nested if-statements for each bracket type, one lookup tells you exactly what opener to expect.def isValid(s: str) -> bool:
stack = []
closeToOpen = { ")" : "(", "]" : "[", "}" : "{" }
for c in s:
if c in closeToOpen:
if stack and stack[-1] == closeToOpen[c]:
stack.pop()
else:
return False
else:
stack.append(c)
return True if not stack else False| Approach | Time | Space | Notes |
|---|---|---|---|
| Brute Force (replace) | O(n²) | O(n) | Up to n passes of O(n) replacements each |
| Stack | O(n) | O(n) | Single pass; stack holds at most n/2 openers |
Any time something must be undone in the reverse order it was done, a stack is the right data structure. Valid Parentheses is just the most visible example.
n ≤ 1000 — even brute force works, but the stack pattern is what interviewers want to see.closeToOpen map has exactly three entries.Every compiler and code editor uses this exact algorithm. When your IDE shows a red squiggle under a mismatched bracket, it ran Valid Parentheses on your source file. JSON parsers, XML validators, and expression evaluators all rely on the same stack-based matching — at much larger scale.
When you see a closing bracket, you must guard against an empty stack before accessing the top. stack and stack[-1] == ... — that stack check first is critical. Without it, you get an IndexError on input like ")".
# Wrong: crashes on empty stack if stack[-1] == closeToOpen[c]: # Correct: guard first if stack and stack[-1] == closeToOpen[c]:
The loop finishing without returning False doesn't mean true. The string"(()" processes all characters without error — but the stack still has one unmatched opener. Always check not stack before returning.
The map is used when you encounter a closing bracket, so it should map closing → opening. Reversing this means you're doing an extra lookup and the logic gets tangled.
")" — closing with empty stack. Should return false."((" — two openers, no closers. Stack non-empty at end → false."[(])" — cross-nested. Should return false."([])" — valid nesting → true."" — valid → true.These all build on the same stack intuition. Min Stack is the most direct follow-up.
Discussion
…