This post has already been read 62 times!

Let's say:

  • '(', '{', '[' are called "openers."
  • ')', '}', ']' are called "closers."

Write an efficient function that tells us whether or not an input string's openers and closers are properly nested.

Examples:

  • "{ [ ] ( ) }" should return True
  • "{ [ ( ] ) }" should return False
  • "{ [ }" should return False

Solution

We iterate through our string, making sure that:

  1. each closer corresponds to the most recently seen, unclosed opener
  2. every opener and closer is in a pair

We use a stack to keep track of the most recently seen, unclosed opener. And if the stack is ever empty when we come to a closer, we know that closer doesn't have an opener.

So as we iterate:

  • If we see an opener, we push it onto the stack.
  • If we see a closer, we check to see if it is the closer for the opener at the top of the stack. If it is, we pop from the stack. If it isn't, or if the stack is empty, we return False.

If we finish iterating and our stack is empty, we know every opener was properly closed.

BrackedValidator
def is_valid(code):
    openers_to_closers = {
        '(' : ')',
        '{' : '}',
        '[' : ']',
    }
    openers = set(openers_to_closers.keys())
    closers = set(openers_to_closers.values())

    openers_stack = []
    for char in code:
        if char in openers:
            openers_stack.append(char)
        elif char in closers:
            if not openers_stack:
                return False
            else:
                last_unclosed_opener = openers_stack.pop()
                # If this closer doesn't correspond to the most recently
                # seen unclosed opener, short-circuit, returning False
                if not openers_to_closers[last_unclosed_opener] == char:
                    return False

    return openers_stack == []


print(is_valid("{[()]})"))
BracketValidator with C#
using System.Collections.Generic;

public static bool IsValid(String code)
{
    var openersToClosers = new Dictionary<char, char>
    {
        { '(', ')' },
        { '[', ']' },
        { '{', '}' }
    };

    var openers = new HashSet<char>(openersToClosers.Keys);
    var closers = new HashSet<char>(openersToClosers.Values);

    var openersStack = new Stack<char>();

    foreach (char c in code)
    {
        if (openers.Contains(c))
        {
            openersStack.Push(c);
        }
        else if (closers.Contains(c))
        {
            if (openersStack.Count == 0)
            {
                return false;
            }
            else
            {
                char lastUnclosedOpener = openersStack.Pop();

                // If this closer doesn't correspond to the most recently
                // seen unclosed opener, short-circuit, returning false
                if (openersToClosers[lastUnclosedOpener] != c)
                {
                    return false;
                }
            }
        }
    }
    return openersStack.Count == 0;
}

Complexity

O(n)O(n)   

time (one iteration through the string), and

O(n)O(n)

space (in the worst case, all of our characters are openers, so we push them all onto the stack).

Leave a Reply

Post Navigation