1. Valid Parentheses (LeetCode)
Model answer
The task
Determine whether a string of opening and closing round, square, and curly brackets is correctly nested and matched. Return a boolean.
Key idea
A closing bracket must match the most recent unmatched opening bracket. A stack captures that order: push openings, and check each closing bracket against the stack’s top.
Approach
- Return
Falseif the string has odd length. - Map each closing bracket to its matching opening bracket.
- Scan the string from left to right.
- Push opening brackets onto the stack.
- For a closing bracket, return
Falseif the stack is empty or its top does not match; otherwise pop. - Return
Trueonly if the stack is empty after the scan.
class Solution:
def isValid(self, s: str) -> bool:
pairs = {")": "(", "]": "[", "}": "{"}
openings = set(pairs.values())
stack = []
for char in s:
if char in openings:
stack.append(char)
else:
# A closing bracket must match the latest unmatched opening.
if not stack or stack[-1] != pairs.get(char):
return False
stack.pop()
# Unmatched opening brackets make the sequence invalid.
return not stack
Complexity:
- Time: O(n), where
nis the string length; each character is processed once. - Space: O(n) in the worst case, when all characters are opening brackets.
Common follow-ups
- How would you support additional bracket types? Add their matching pairs to the map.
- Can you stop early? Yes; return
Falseas soon as a closing bracket mismatches or has no opening bracket. - What if the input includes non-bracket characters? Define how to handle them, then either ignore them or reject them during the scan.