Check the brackets in a config template
A re-solve is due. Start from a blank template and solve it without the editorial. That is what makes the pattern stick.
The problem
A config template uses (), [] and {}. Before it is rendered, check that every bracket closes the most recent bracket still open, with the matching kind, and that nothing is left open.
Other characters do not matter. Return true if the brackets are balanced and false otherwise.
- 0 ≤ text.length ≤ 200,000
Examples
balanced("{ \"ports\": [80, 443], \"tls\": (on) }")returnstruebalanced("([)]")returnsfalseThe ] closes a ( that is still open inside.balanced("{{")returnsfalseLeft open.
Hints
Hint 1 of 2
When a closing bracket arrives, which opening bracket must it match?
Hint 2 of 2
Push each opening bracket. On a closing bracket, pop and compare. At the end the stack must be empty.
Editorial
Opens once you solve the problem, or after three checked attempts.
Read the editorial and a reference solution
Counting each kind of bracket is not enough: ([)] has one of each opening and closing, but the ] arrives while a ( opened after the [ is still open. What matters is order, and the bracket a closing one must match is always the most recent one still open. That is a stack.
Push opening brackets. On a closing bracket, pop and compare with the matching opening kind; popping an empty array gives undefined, which matches nothing, so a stray } fails too.
At the end, anything left on the stack opened and never closed, so the answer is whether the stack is empty.
function balanced(text) {
const open = { ')': '(', ']': '[', '}': '{' };
const stack = [];
for (const ch of text) {
if (ch === '(' || ch === '[' || ch === '{') stack.push(ch);
else if (ch in open) {
if (stack.pop() !== open[ch]) return false;
}
}
return stack.length === 0;
}Complexity. O(n) time, O(n) space in the worst case of deep nesting.
Your solution
TypeScript types are removed before the tests run, not checked: the tests judge what the code does.
Tab indents. Press Esc, then Tab, to leave the editor. Ctrl+Enter runs the examples.