Data structures problem 5 of 30

Balanced brackets

Data structures
Easy

Write is_balanced(s) that returns True if every bracket in s is closed by the same type of bracket in the right order. The string contains only ()[]{}.

is_balanced("([]{})")  # True
is_balanced("([)]")    # False
is_balanced("((")      # False

Show hint

The most recently opened bracket must be the first one closed. Which data structure gives you "last in, first out"?

Show solution

def is_balanced(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
        else:
            stack.append(ch)
    return not stack

Push every opening bracket. On a closing bracket, the top of the stack must be its partner. At the end the stack must be empty, otherwise something was never closed. O(n) time.

Want a problem like this every day? See today's problem and keep a streak going.