Leetcode 20. Valid Parentheses or "That day when life happened"
Some months before coming to the United States, I had an interview for a tech-consulting firm. There, I was asked to solve the LeetCode (LC) problem on Valid Parentheses. The following is a mixture of a story and the solutions to the problem.
After reaching out and applying to the company, I felt excited that I had finally gotten another interview. I was given two weeks to prepare. Adrenaline was my new blood. Coffee was not even necessary. The joy of preparing and trying was enough to keep me awake for the whole day.
At that time, I didn't know about the 75 blind problems (I was too green). So some basic google, brought me into the most common questions they could ask me. The interview was planned to last between 5 to 6 hours. It was the perfect example of a one-shot interview.
It started great. For the first two hours, I excelled. I was radiating happiness. Little did I know, that during the coding part things would go in a different direction.
Before jumping into the general problem, they first gave me a simplified version of it.
Write a code that can let me know if a string full of normal parentheses '(' or ')' is following the rules of opening and closing (i.e. for each opening parentheses there is a corresponding closing one directly at the same level).
Examples of true scenarios: '(())', '()()','(()()(()))'.
Examples of false scenarios: '(', '(()', ')('.
It was my first time with this problem. My first approach consisted of assigning +1 or -1 to an opening or a closing parentheses, respectively. With a linear complexity, I would find out if at any given moment my tracker became negative. If that was the case, then, I would return a False. After completing the loop, I would only return a True if at the end of the string my sum was a zero and false if not.
I felt great. I had a working answer.
But, then. Things got messy. They asked me to generalize my approach to a situation where I had the three different types of parentheses. What I didn't realize at that moment was that "generalize your solution" to the following situation, implicitly and explicitly meant "take what you have done and make it more general". So I got stuck. I created three negative and positive markers for each kind of parentheses. Many if statements started to appear. Also, I had drunk so much water by that time that I needed to go to the toilet. Oh, man, it was chaos.
At a given point, they suggested me to think again, in terms of something new. But my mind, could not forget my initial approach. I was trying to think in terms of numbers. And that was my mistake. My first solution had been at the same time a death-end.
After the interview finished and I could finally relaxed. It didn't take me more than a minute to come to a first solution. I called it the bubble blower. Write a while loop where you replace every '()', '[]', and '{}' with an empty string. If the while loop ends because the string is empty, you return True. However, when there are no bubbles you can blow but the string is not empty, then, your while loop must be able to recognize this and return a False. It was not the most efficient solution, but it was already a solution. I then came to other kinds of solutions. What this showed me was that, sometimes if you are not given, from the very beginning, the general problem it can push you to a death-end solution that will only work in the simplest scenarios and that will always hinder you from understanding the general setup (specially under pressure).
So, now, let's jump into the most common solution.
The solution is about walking character after character, and sequentially storing them. Each time you face a closing type of parentheses, you ask yourself if the previous character corresponds to an open and similar type of parenthesis. If that's the case, you end up popping from your storage the last element and you don't save the present character, if not you return False. For all other cases, you append them to the list where you are storing the individual string elements. After the for loop ends, you return the negative of your list. If it's empty, then it becomes True, if not, then it's False.
Leetcode 20.
Statement:
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
- Every close bracket has a corresponding open bracket of the same type.
Constraints:
1 <= s.length <= 104sconsists of parentheses only'()[]{}'
Solution:
opposites = {'{':'}','[':']','(':')'}
closing_cases = [')',']','}']
storage = []
for element in s:
if element in closing_cases:
if not storage or opposites[storage[-1]] != element:
return False
storage.pop()
else:
storage.append(element)
return not storage