A string s contains only the six characters (, ), [, ], { and }.
Return true if the brackets are balanced: every opening bracket is closed by a bracket of the
same kind, closings happen in the reverse order of openings (so ([)] is not balanced), and no
closing bracket appears without an opening one before it. Return false otherwise.
Example 1
- Input
- s = "{[]()}"
- Output
- true
[] and () close inside the braces, and the braces close last.Example 2
- Input
- s = "([)]"
- Output
- false
) arrives while [ is the most recent open bracket.Example 3
- Input
- s = "(("
- Output
- false
Constraints
sholds 1 to 10⁴ characters.- Every character is one of
()[]{}.
Show the pattern
Stack
Every closing bracket must match the most recent opening bracket that is still open. "Most recent first" is exactly what a stack gives you.
See stack in a visualiserShow the approach
Scan the string with a stack of brackets that are still open. Push every opening bracket. For a closing bracket, the stack's top must be its partner: if the stack is empty or the top is a different kind, the string is unbalanced; otherwise pop it. The string is balanced exactly when the stack is empty at the end.
Time: O(n) · Space: O(n)