Description
Determine whether a string of round, square, and curly brackets is properly nested and balanced.
Solution
def is_valid(s):
stack = []
pairs = {')':'(', ']':'[', '}':'{'}
for char in s:
if char in pairs:
if not stack or stack.pop() != pairs[char]:
return False
else:
stack.append(char)
return not stackExamples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
["([])"]- Output
true
Each closing bracket matches the most recent opener.
Example 2
- Input
["([)]"]- Output
false
The round closer crosses an unmatched square bracket.
Example 3
- Input
["(("]- Output
false
Open brackets remain at the end.
Approach
Push opening brackets; every closer must match the most recent unmatched opener.
Time & space
O(n) time; O(n) space. Here n is the input length.