Check if brackets are balanced
DSA, Easy
Which structure or algorithm, and what does it cost.
You get a string made only of the characters (, ), [, ], {, }. Return true if every opening bracket is closed by a bracket of the same kind, and brackets close in the reverse order they opened. Otherwise return false. The empty string is balanced.
Examples
Input "()[]{}"
Output true
Why each pair closes right after it opens.
Input "{[()]}"
Output true
Why the inner pair closes first, then the next one out.
Input "([)]"
Output false
Why every kind has the right count, but
] closes while ( is still the most recent open bracket.Constraints
- 0 <= length of the string <= 100,000.
- Only the six bracket characters appear.
Your answer must contain
- Why counting each kind of bracket is not enough; the method; code; time and memory cost; a hand trace of example 3.