🛑️ This won't make any sense unless you're familiar with the problem explanation on LeetCode: https://leetcode.com/problems/valid-parentheses
Simplified Problem
For the simplest case of a string with length 2 and only (
or )
, there are four options:
(), )(, ((, ))
How can we decide that the first one is the only valid one? I think about this problem as trying to find when it is invalid rather than valid. So we need to consider the ways a string could be invalid, and if it passes all those checks, we can consider it valid.
There are exactly two ways a string can be invalid:
- We reach a closing bracket that hasn't yet been opened (second and fourth cases above)
- We reach the end of the string with open brackets that aren't closed (third case above)
So, the solution here is to use a stack that we add to whenever we encounter an open bracket. To check the above conditions:
- When we reach a closing bracket, if it doesn't match the top of the stack, the string is invalid.
- If we've processed the whole string and there are elements left in our stack, the string is invalid.
Example With Valid String
This is how we will process a string.
We start with an empty stack:
stack: empty
string: (([]){}[])
current: empty
We then look at the first element of the string. In this case, it's an opening bracket, so we can put it onto the stack and continue.
stack: (
string: (([]){}[])
^
We encounter a few opening brackets, so let's fast-forward through them.
We just add to stack every time:
stack: (([
string: (([]){}[])
^
Now, we've hit our first closing bracket. So we look at the top of the stack and see if it matches:
stack: (([
string: (([]){}[])
^
It does, so we can continue. Remove the match from the stack and step forward. We're on another closing bracket, so we again compare to the stack:
stack: ((
string: (([]){}[])
^
Hopefully you can see that this will work for the rest of the string. At the end, we can confidently return true
because the stack is empty and we didn't encounter any issues.
Example With Invalid String
Let's look at what would happen with a bad string. I've skipped the first few elements (you can see they're already on the stack):
stack: ((
string: ((]){}[])
^
In this case, we've encountered a closing bracket that doesn't match the top of the stack. Therefore, we can return false
.
What about the second way we can fail, where there are too many opening brackets? Here's what it would look like when we reach the end of the string:
stack: ({
string: ((){
In that case, we can return false
at the end of the function if len(stack) > 0
and true
otherwise. Therefore we can simply return len(stack) == 0
.
Final Solution
I hope my code is simple and clear after that explanation. The only thing I do differently is instead of storing the open brackets on the stack, I store the matches that we're looking for. Please let me know if you have any questions about how it works.
func isValid(s string) bool {
// if the string isn't of even length,
// it can't be valid so we can return early
if len(s)%2 != 0 {
return false
}
// set up stack and map
st := []rune{}
open := map[rune]rune{
'(': ')',
'[': ']',
'{': '}',
}
// loop over string
for _, r := range s {
// if the current character is in the open map,
// put its closer into the stack and continue
if closer, ok := open[r]; ok {
st = append(st, closer)
continue
}
// otherwise, we're dealing with a closer
// check to make sure the stack isn't empty
// and whether the top of the stack matches
// the current character
l := len(st) - 1
if l < 0 || r != st[l] {
return false
}
// take the last element off the stack
st = st[:l]
}
// if the stack is empty, return true, otherwise false
return len(st) == 0
}
Top comments (1)
Very nice and easy to follow solution, well done!
I believe that the results might mislead someone, as in the example, the stack stores the opening brackets, while the code shows that the closing brackets are being stored!