# Leetcode Problem: Valid Parenthesis

programming-exercises (5 Part Series)

## 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 { "" }


programming-exercises (5 Part Series)

### Discussion   