JavaScriptMediumStrings20 min
Validate balanced brackets
Return whether a string of brackets (), [] and {} is correctly nested and balanced. All input is valid JSON satisfying the constraints; do not mutate the meaning of values through type coercion. Interviewers use this problem to assess match closing brackets with the most recent opening bracket.
Input
A JSON string on stdin.
Output
Print one compact JSON value: a boolean.
Constraints
0 <= string length <= 10000; only characters ()[]{} are allowed.
Example
Input
"{[()]}"Output
true
Example 2 input
"()[]{}"Output
true
Boundary case: An empty bracket string is balanced
Public test cases (2)
Input
"{[()]}"Expected output
true
Input
"([)]"
Expected output
false
Hints (2)
- Use a stack to remember unclosed brackets
- An empty bracket string is balanced
Target complexity: time O(n) · space O(n)