The Leetcode problem Valid Parenthesis is a very popular interview problem asked at companies such as Amazon and Facebook.
They give you a string that can include curly braces, square brackets, and parentheses. Test examples and output given in the problem statement are shown below:
One edge case to consider is if there are only opening “parentheses” in the string. Another edge case to consider is what if there is only 1 character? The constraints in the problem mention there will at least be 1 character and we can be sure it will only be curly braces, square brackets, and parentheses.
The approach I took for this problem was to make a HashMap of closing “parentheses” characters as the keys and their open counterparts as the values. I will make a character array from the string, to loop through each character. I will use a stack to hold the opening “parenthesis”.
Check if there is a closing character.
If it is not a closing character, add it to the Stack (It is an opening character).
3.If there is a closing character and the Stack is empty, return false.
If there is a closing character and the stack is not empty, use it as a key to the HashMap to get the matching opening character. Pop from the stack and compare it with the value you got from the HashMap. If they are not equal, return false.
After looping through the array, we can handle the two edge cases by checking the size of the Stack. If it is not empty return false.
Finally, return true if the string of parentheses is valid.
The last step handles a string only having opening parenthesis because we will only add to the stack if there are opening characters and only pop if there are closing characters. This also handles the edge case of having only 1 character (in the loop).
My final code:
Codelab version of this solution:
https://cmcoffeedev.com/codelabs/leetcode-valid-parentheses/index.html?index=..%2F..index#0
Video solution:
Top comments (0)