Write is_balanced(s: str) -> bool that returns True if every bracket in s is closed by the matching kind, in the right order.
- The bracket pairs are
(),[]and{}. - Every other character is ignored.
- Brackets must nest properly: the most recently opened bracket that is still open must be the next one closed.
is_balanced("f(a[i], {k: v})") # True
is_balanced("([)]") # False ("[" is still open when ")" arrives)
is_balanced("(()") # False (one "(" is never closed)
is_balanced("") # True
Constraints: len(s) <= 10**5. One pass over the string, O(n).
Show hint
push each opening bracket onto a list; on a closing bracket the stack must be non-empty and its top must be the matching opener (pop it), and at the end the stack must be empty.