Problem
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.An input string is valid if:1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.Note that an empty string is also considered valid.Example 1:Input: "()"
Output: trueExample 2:Input: "()[]{}"
Output: trueExample 3:Input: "(]"
Output: falseExample 4:Input: "([)]"
Output: falseExample 5:Input: "{[]}"
Output: true
Approach
What should I understand and be mindful of?
Key Points (referred to as KP throughout the explanation):
- Open brackets must be closed by the same type of brackets. (“[}” is invalid)
- Open brackets must be closed in the correct order. ( “({[)}]” is invalid, even though each type of bracket has a pair of openers and closers).
- Empty string is valid.
- Parentheses can be nested.
Possible Clarifying Question(s) to Ask:
- Can the strings contain white spaces? (Let’s assume no white spaces for this explanation)
Generate Examples:
- Input: “((())”
Output: false
Explanation: Different amount of openers (3) and closers (2). An additional closer is needed to balance out the parentheses. - Input: “())”
Output: false
Explanation: One extra closer. Nothing to pop since there is only one opener, compared to two closers.
Make sure you understand the problem before moving on!
How should I approach this problem?
Simplify
If you cannot think of an approach early on, try thinking of a simpler version of this problem — simplifying the question is one of the best strategies to get unstuck!
When I think of a simpler version of this problem, the easiest one that comes to my mind is restricting the type of parentheses to just one — let’s make it “(“ and “)”.
With our simpler version, how would you naturally validate the strings? If I were you, I would scan from the beginning of the string and keep an eye on any valid opener and closer pair. If I see consecutive openers, I’ll keep a count on how many there are and keep traversing the string to check if there are any closers that can complement the consecutive openers.
Great! That sounds like a good start. In fact, that is the algorithm we will work with!
We can use a counter to keep the count of openers we have seen so far. As we traverse the string, we will increment the counter by one if we see an opener, and decrement the counter by one if we see a closer.
Now how do we know if or when a string becomes invalid?
There are two scenarios:
- When we encounter a closer and the counter is already 0.
Meaning: We have a closer but there are not enough openers to cancel each other out (or pair up). - When the counter is greater than 0 but we are already at the end.
Meaning: We have reached the end of the string but the string did not enough closer to cancel the openers out.
Essentially, the string is invalid whenever the counter is less than 0 or if the counter is not 0 by the end of the traversal.
SCENARIO #1(()))()
counter = 0(()))()
^
counter = 1(()))()
^
counter = 2(()))()
^
counter = 1(()))()
^
counter = 0
(()))()
^
counter = -1
INVALID---------------------------------SCENARIO #2((())
counter = 0((())
^
counter = 1((())
^
counter = 2((())
^
counter = 3((())
^
counter = 2((())
^
counter = 1end of string but counter > 0
INVALID
Back to the Original Problem
Now, we can base the solution to our original problem off of what we learned here. Let’s go back to the original problem now.
Why can’t we use the same approach?
Our first approach worked because all the parentheses were of the same type. We assumed that the closer we encountered was a complementing bracket. But since we only keep track of the number of “an” opener, we cannot guarantee that our closer is exactly the same type.
What if we maintain a separate counter for each type of parenthesis?
That won’t work either since when we encounter a closer, we still have to make sure that there was a matching opener right before the closer.
So what’s a better approach?
We still need to check if we had perfect matching for each opener and closer. Thus, whatever method we use, the method should indicate that all parentheses were matched by the time we traversed to the end.
Let’s take a look at our bag of tricks. I encourage you to take a look at each data structure, algorithm, technique, and question, and throw it at the question! See if any of them is applicable to our problem.
My first thought here is: stacks.
Why?
I mentioned earlier that we want to “somehow check that the last opener is exactly the same type as our closer”. As in, we want to get the item that was added last, or last-in-last-out (LIFO). Stack will fulfill our requirements.
Let’s visualize it.
VALID EXAMPLE
{ [ [] {} ] } { () () }
| | | | -> level 1
| | || || -> level 2
|| || -> level 3At each bar, the stack is...
push {
push {[
push {[[ (we encountered a ']' and it matches our last pushed item)
pop {[
push {[{ (we encountered a '}' and it matches our last pushed item)
pop {[
pop {
empty
push {
push {(
pop {
push {(
pop {
emptyINVALID EXAMPLE
{ [ ) }
| -> level 1
| | -> level 2At each bar, the stack is...
push {
push {[
pop {[
(we encountered a ')' and it does not match our last pushed item, so we return False)
Our algorithm will be:
- Traverse the string and when we encounter an opener, push it onto the stack.
- When we encounter a closer, we check if the last element we pushed onto the stack is a complement of it. If it is, we pop the last element off the stack and we move on. Else, we can immediately return False as the string is now invalid.
- At the end, we check that all openers were cancelled out with the closers in the string, by checking if the stack is empty. If it is, the string is valid, else, invalid.
In code, it will look like this:
What is the complexity?
Time: O(N), since we will have to traverse each character at least once to confirm.
Space: O(N), in the worst case, where all the brackets are openers, we may have to push all of them before we realize it is invalid.
