clueless coding // TODO: be smarter

LeetCode 20. Valid Parentheses: Explanation and C++ Solution

Problem Statement


Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.

The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not.

Function Signature:
  C++
    bool isValid(string input) {...}

Inputs:
  input = ([{}])

Outputs:
  true

Inputs:
  input = ([{)}]

Outputs:
  false



Solution #1 (optimal): Stack

O(N) runtime, O(N) memory


Our first instinct might be to simply count the number of each type of brace - the number of closed brackets should always equal the number of open brackets, closed parens should match open parens, etc. However, while that’s true, it’s not a complete solution. What if we had the following?

Inputs:
  input = {[}]

count { == 1, count } == 1
count [ == 1, count ] == 1

While the counts match, the above statement is not a well-formed string because of the order.

We can think about the problem like so: for every closing character, we want the last seen UNMATCHED open character to match it. For example, applying people logic to the the string ([{}])

Inputs:
  input = ([{}])

Parsing from left to right:
  (:
    open character
  [:
    open character
  {:
    open character
  }:
    closed character!
    what was the most recently seen unmatched open character?
    it was a '{'!
        it matches, continue!
  ]:
    closed character!
    what was the most recently seen unmatched open character?
    the most recently seen open character was a '{'
        it was already matched
    the next most recently seen open character was a '['
        it matches, continue!
  ):
    closed character!
    what was the most recently seen unmatched open character?
    the two most recently seen characters were '[' and '{',
        they were both already matched
    the next most recently seen open character was a '('
        it matches, so continue!
  no errors, so we know the string is well-formed

This is a pretty simple approach, but does it really check for order?

Inputs:
  input = {[}]

Parsing from left to right:
  {:
    open character
  [:
    open character
  }:
    closed character!
    what was the most recently seen unmatched open character?
    it was a '['
        this is not a match, ERROR

We’ve solved the problem with our original count solution. Great! But how do we code this? It seems a little unfair to use ‘people logic’ - in particular, the ‘what was the most recently seen unmatched character’ seems like a very heavy statement that would be complicated to code.

Contrary to that, though, we know a data structure perfect for the task: the stack! We’ll use it to figure out the ‘most recently seen’ - a stack enables us to go through all the open characters in the reverse order that we’ve seen them.

bool isValid(string input) {

    stack stac; // create a stack to record items

    // parse string from left to right
    for (int i = 0; i < input.length(); i++) {
        // if open character, push it onto stack
        if (input[i] == '[' || input[i] == '(' ||
            input[i] == '{') {
            stac.push(input[i])
        }
        // otherwise, find most recent and verify matching
        else if (input[i] == ']' && stac.top() == '[') {
            stac.pop();
        }
        else if (input[i] == '}') {
            stac.pop();
        }
        else if (input[i] == ')') {
            stac.pop();
        }
        // closed character that did not match most recent
        else {
            return false
        }
    }

    // we made it, no errors!
    if (stac.size() == 0) return true;
    else return false;
}

Our algorithm matches our ‘people logic’ pretty well - if we see an open character, remember them in most-recent order, i.e. reverse order that we saw them. We use a stack to do this, as the top of the stack will always have the most recently seen open character. When we hit a closed character, we simply look at the top of the stack and see if it’s a valid match. If not, we quit. If so, we continue. Simple.

We also need to remember to pop from the stack if we find a valid match, simply because every open character needs to match only a single time. As soon as it matches, we start looking to match the next character.

You’ll notice that we have a couple lines of code at the end that we didn’t discuss before. That’s simple a size check - if our stack was not empty at the end of our loop, we know that some open characters were not matched. While there were no errors (because we hadn’t hit return false in the loop), there are open characters that are left hanging - try the algorithm out on the string ( and you’ll understand why the size check is needed.

So - we have a working algorithm, but it’s not very aesthetically pleasing - there are a lot of repeated statements (looking at you, stac.pop()) that we could clean up. We’ll use a simple dictionary to keep track of ‘matching’ characters to make it a little nicer:

bool isValid(string input) {

    unordered_map<char, char> matches({
                                        {'}', '{'},
                                        {')', '('},
                                        {']', '['}
                                      });

    stack stac; // create a stack to record items

    // parse string from left to right
    for (int i = 0; i < input.length(); i++) {
        // if open character, push it onto stack
        if (input[i] == '[' || input[i] == '(' ||
            input[i] == '{') {
            stac.push(input[i])
        }
        // otherwise, find most recent and verify matching
        else if (stac.top() == matches[input[i]]) {
            stac.pop();
        }
        else {
            return false;
        }
    }
    return stac.size() == 0;

}

O(N) runtime - we only operate on each element once.

O(N) memory - in the worst case, we have to store a piece information for every single character in the input - in the string (((, we’d store the entire input.