Problem
Bracket validation shows up in code editors, linters, template parsers and form inputs that accept expressions, and checking balanced parentheses in JavaScript is a classic warm-up in frontend interviews.
Write a function isBalanced(str) that returns true if every opening bracket in str has a matching closing bracket of the same type, closed in the correct order, and false otherwise.
Requirements
- Support three bracket pairs:
(),[]and{}. - Brackets must close in the reverse order they were opened:
"([)]"is not balanced. - A closing bracket with no matching opener makes the string unbalanced.
- Any opener left unclosed at the end makes the string unbalanced.
- Ignore every character that is not a bracket (letters, digits, spaces, operators).
- An empty string is balanced.
- Run in linear time with respect to the length of the input.
Example
isBalanced("()[]{}"); // true
isBalanced("function f() { return [1, 2]; }"); // true
isBalanced("([)]"); // false
isBalanced("]"); // false
isBalanced("{["); // false
isBalanced(""); // true
Follow-ups
- How would you return the index of the first offending character instead of a boolean?
- How would you support angle brackets
<>or a configurable set of pairs? - What changes if brackets inside string literals like
"("must be ignored?