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.


Leave a Reply

Your email address will not be published. Required fields are marked *