Solving Valid Parentheses
This week will take a look at a popular leetcode problem and try to solve it with a data structure that we are familiar with. This question is extremely relevant to every day coding. Anyone who has touched a code editor knows the frustration and the feeling of missing a bracket, parentheses or a curly brace. Fortunately, error messages would tell us if we are missing any, and then would go searching for it.
In this leetcode problem, we are pretty much doing the same thing. If given a string, we need to determine if it has all its parentheses (or brackets) closed correctly. A string is valid if
- Open brackets must be closed by the same type of brackets.
- Open brackets must be close in the correct order.
Now lets take a look at some examples of valid and invalid closing parentheses.
As we can see, each bracket or parentheses has it corresponding closer. Right away we can think a few edge cases. The first thing is that a valid parentheses is always a pair (2), meaning it will always be greater than zero. In order to have a valid parentheses pair, the length of the string must be a multiple of two. Although not all even number string is parenthesized correctly, all correctly parenthesized strings are even.
In this problem we would be using stack and map (or hashmap). Lets first setup our map or key/value pairs. We first create a map of these parentheses with the opening parentheses as the key, and the closing parentheses as the value. We will be checking against this map to validate the values from the string and the stack (which we will create). after then declare an empty array to setup our stack. Stack employs a common operational concept call LIFO(last in first out)/ FILO(first in last out). We will be using a stack to keep track of the characters we will be pushing (adding) and popping (removing) from the array.
Starting from the beginning of the string, every character will be checked until we reach the end or when the closing parentheses doesn't match. If the character is an opening parentheses, it gets pushed it to stack. If our current character is a closing parentheses, we will then check the last entry in the stack. If the last entry is an opening parentheses of the same type, will can then pop that from the stack. If doesn’t match the our map, we will return false. When we have checked all the characters and they all match, the stack should be empty once again.
Since we are looping over every character in the string, the time complexity will be O(n). The space complexity would be O(n) as well. This is because we are individually adding each value in to our stack, and we could potentially only push values in and not pop anything out if the string is not a valid parentheses.
