The Paired Doors

An easy Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
easy
Seniority
L3
Asked in
Afiniti

Problem

A linter for our query templates rejects expressions whose grouping symbols don't line up. Given a string s drawn only from the characters '()[]{}', return True when each closing bracket matches the most recently opened bracket of the same kind and nothing is left open, and False otherwise. An empty string counts as balanced.

Every door you open is a promise to close it, in order.

Example 1

Input:

s = "()[]{}"

Output:

true

Example 2

Input:

s = "([)]"

Output:

false

Worked solution and explanation

What this really is

Strip the syntax-validation costume and this is a last-in-first-out matching problem. The skill being probed: can you track open brackets so the correct one is forced to close first? Everyone reaches for a stack within seconds. What actually separates candidates is the two guards around the pop. A closer can arrive when nothing is open, and openers can still be sitting on the stack when the string ends. Miss either guard and ([)] or ((( sails through as valid.

How to build it

Step 1: Map every closer to its opener

Build one dict that sends each closer to the opener it must match: ) to (, ] to [, } to {. Membership in this dict is also how you tell a closer from an opener in a single check.

Step 2: Push openers, defer the decision

An opener carries no decision yet, so just remember it: push it onto the stack and move on. The stack is your record of what is still waiting to be closed, in the exact order it was opened.

Step 3: On a closer, the top must match

On a closer, the only correct partner is the top of the stack. Before you touch the top, confirm the stack is non-empty, otherwise a leading ) blows up with an IndexError. Then pop and compare: a mismatch means the nesting is wrong, return False immediately.

Step 4: Finish only when the stack is empty

Reaching the end is not enough. If anything is left on the stack, those openers never closed, so the answer is False. The empty-string case falls out of this for free: nothing pushed, stack empty, True.

The solution

Stack-based bracket matching
def validate_brackets(s: str) -> bool:
    open_for = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in open_for:
            if not stack or stack.pop() != open_for[ch]:
                return False
        else:
            stack.append(ch)
    return not stack

One pass, the two guards folded into a single short-circuit condition.

Common follow-up questions