Check a bracket string ()[]{} is balanced
Implement isValid(s) for a string of ()[]{} characters. Return true when every opening bracket is closed by one of the same type and in the correct order. Requirements: O(n) time. Handle the edge cases — a closer arriving with nothing open (e.g. "]") is invalid, and leftover unclosed openers at the end (e.g. "(") are invalid too.
func isValid(s string) bool {
// your code here
return false
}Write the implementation.
Push each opener onto a stack; on a closer, pop and verify it matches the expected opener — bail out early on mismatch or empty stack. The string is valid only if every closer matched and the stack is empty at the end. Runs in O(n) time and O(n) space.
- ✗Returning true at the end without checking the stack is empty — leaves unmatched openers
- ✗Popping from an empty stack when a closer arrives first, causing an index panic
- ✗Comparing closer-to-closer instead of mapping each closer to its expected opener
- →How would you adapt this to report the index of the first unmatched bracket?
- →Why does early return on mismatch keep the worst case at O(n)?
Task
The input is a string of ()[]{} characters. It is valid when every opening bracket is closed by one of the same type and in the right order.
// "[]({})" — valid
// "[]{(})" — invalid
func isValid(s string) bool {
// closer → expected opener
pairs := map[byte]byte{')': '(', ']': '[', '}': '{'}
stack := make([]byte, 0, len(s))
for i := 0; i < len(s); i++ {
c := s[i]
if open, isCloser := pairs[c]; isCloser {
// On a closer: stack non-empty and top is the matching opener.
if len(stack) == 0 || stack[len(stack)-1] != open {
return false
}
stack = stack[:len(stack)-1] // pop
} else {
stack = append(stack, c) // push the opener
}
}
return len(stack) == 0 // all closed
}Key invariants: early return on mismatch, the empty-stack check before each pop, and the final len(stack) == 0 check. Complexity is O(n) time and O(n) space.
