Code Corner: Bracket Matching

Problem

Given a string with brackets check to see if the brackets are properly nested.

Source

Example

[] = return 1
() => 1
)( => 0
({)} => 0
'' => 1

My Solution

Classic stack problem. Didn’t need to brute first. The idea is you create a stack and loop through each character pushing and popping.

You push if it’s an opening bracket and pop if it’s a closing bracket.

On each pop, you check that the popped value is the match for the current character. If it’s not, return 0 otherwise, continue.

After the loop you now check the stack, if it’s empty then everything was nested correctly. If it’s not empty then return 0. The code looks like:

function solution(S) { const bracketStack = [] const closingBracketMap = { ')': '(', ']': '[', '}': '{', } const openingBracketSet = new Set("({[") for (const character of S) { if(openingBracketSet.has(character)){ bracketStack.push(character) } else if (character in closingBracketMap){ if ( bracketStack.pop() !== closingBracketMap[character]){ return 0 } } } return bracketStack.length === 0 ? 1 : 0 }
Code language: JavaScript (javascript)

And that’s all she wrote.