Leetcode Problem: Valid Parenthesis

Background

Recently, I decided to solve some of the problems in leetcode.com for fun and practicing my java which I have not used in a while. I decided to document my thought process as I solve these problems. You can find some of the other solutions in the series table above this section.

Problem

Valid Parentheses
Given a string of parentheses determine if the string is valid. The string is valid if and only if, the opening and the closing parentheses match.

For e.g.

{([])} - valid
{{{ - Invalid
()() - Valid
({) - Invalid

Solution

I know the answer to this problem from my college intro to Algo class. The trick here is to use a Stack data structure. One of the first benefits I remember of stacks was to use stacks to verify certain kinds of grammar which is what this question is about. Verifying a grammar of parentheses.

The pseudo algorithm is:

1. Walk through every character in the array.
2. If the character is a opening parentheses push into the array.
3. If the character is a closing parentheses pop the top element in the array.
4. If it is the corresponding opening parentheses, move on ; else return false (fail quick)
5. If all elements have been processed, then the string is valid if the stack is empty.

Coding the solution

The following is the first version of the solution that I wrote:

After I verified that this works, I wanted to clean up a bit. A easy win would be to flip the inner if loop so that I don't have to keep two maps. Also that would take care of invalid (non parentheses) characters. So I got here:

Sidebar

One other difference in the above two solution is that I have a special case for empty string in the second case. The reason for is two-fold:

1. First of course is fail early. No need to try and work on string when we already know the result.
2. Second is something I learned today (#til). In java if you split an empty string by an empty string, it results in an array of length 1 with an empty string as the only element. 😮

Here is an e.g.

jshell> "".split("")
$1 ==> String[1] { "" }