Leetcode 20: Valid Parentheses
Leetcode 20: Valid Parentheses is a great problem.
It is a perfect introduction to using a ‘stack.’.
The goal is to be able to check that a string has matching opening and closing parenthesis, either parenthesis “(”, brackets “{”, or squares (square brackets?) “[”. i.e. “(){}[]” Is valid. “(]” is not valid as these two open and close brackets are not of the same type. “(” is matched by “)” and not “]”.
Let’s break down the problem line by line.
By the by, unlike LeetCode, I will be using a static method, just because.
static bool IsValid(string s) {
}
The first thing we can do is exit immediately if we are not given an even number of characters. A string that should return true will always have an even number of characters. An odd number of characters indicates that one of the opened brackets is not closed. i.e. string likes ‘()[])’. Or… that we have extra closing brackets like `(}}})
static bool IsValid(string s) {
if (s.Length % 2 != 0) return false;
}
Now before we iterate through our input string - we introduce our heroic stack!
Stack<char> stack = new Stack<char>();
Our code so far…
static bool IsValid(string s) {
if (s.Length % 2 != 0) return false;
Stack<char> stack = new Stack<char>();
}
Next, let’s take any opening parenthesis / braces and put it on top of our stack.
if (c == '(' || c == '[' || c == '{') {
stack.Push(c);
Now, every time there is a ‘(’ – the stack lets us know we have an open parenthesis which we need to be close. If a bracket character is still on the stack – it is not closed yet. Think of it like a stack of open order tickets at a diner. When the food is delivered - an open ticket is taken from on top of the stack. The ‘stack of paper’ in this case, keeps track of what is left open.
Let’s use a for each loop to iterate through each character in the string.
foreach (char c in s) {
To check whether something is on the stack we Peek at the stack. `Peek()’ lets us see what is on top of the stack, without actually popping (removing) anything from the stack.
Finally, we have to check whether or not the stack is empty. If we ‘Peek’ at an empty stack, it will cause an error.
} else if (c == ')' && stack.Count != 0 && stack.Peek() == '(') {
Our code so far…
static bool IsValid(string s) {
if (s.Length % 2 != 0) return false;
Stack<char> stack = new Stack<char>();
foreach (char c in s) {
if (c == '(' || c == '[' || c == '{') {
stack.Push(c);
} else if (c == ')' && stack.Count != 0 && stack.Peek() == '(') {
We can then check all other closed braces against what might be on the stack, using else if statements (terrible style but whatevs…)
} else if (c == ')' && stack.Count != 0 && stack.Peek() == '(') {
stack.Pop();
} else if (c == ']' && stack.Count != 0 && stack.Peek() == '[') {
stack.Pop();
} else if (c == '}' && stack.Count != 0 && stack.Peek() == '{') {
stack.Pop();
}
There is something else we have to do with our stack. We want to return false if there are too many closing braces like, (}}).
To catch this edge case, we need a final else statement that pushes, extra closing braces onto the stack. We tell our program this: anything not an opening brace, or anything not a closing brace, with an opening brace on the stack, push to the stack.
} else {
stack.Push(c);
}
Our code so far…
static bool IsValid(string s) {
if (s.Length % 2 != 0) return false;
Stack<char> stack = new Stack<char>();
foreach (char c in s) {
if (c == '(' || c == '[' || c == '{') {
stack.Push(c);
} else if (c == ')' && stack.Count != 0 && stack.Peek() == '(') {
stack.Pop();
} else if (c == ']' && stack.Count != 0 && stack.Peek() == '[') {
stack.Pop();
} else if (c == '}' && stack.Count != 0 && stack.Peek() == '{') {
stack.Pop();
} else {
stack.Push(c);
}
To actually decide whether we should return true or false is simple. If the stack is completely empty return true. An empty stack means that every opening brace was correctly closed.
If there is stuff left on the stack, that means we have some braces which were left open and not closed. It could also mean we have extra closing braces like (}}).
Here is the final solution:
static bool IsValid(string s) {
if (s.Length % 2 != 0) return false;
Stack<char> stack = new Stack<char>();
foreach (char c in s) {
if (c == '(' || c == '[' || c == '{') {
stack.Push(c);
} else if (c == ')' && stack.Count != 0 && stack.Peek() == '(') {
stack.Pop();
} else if (c == ']' && stack.Count != 0 && stack.Peek() == '[') {
stack.Pop();
} else if (c == '}' && stack.Count != 0 && stack.Peek() == '{') {
stack.Pop();
} else {
stack.Push(c);
}
}
if (stack.Count == 0) {
return true;
} else {
return false;
}
}
A fancy pants solution with a dictionary
We can implement essentially the same solution, but this time, we use a dictionary tomap what opening braces go with what closing braces.
static bool IsValid(string s) {
if (s.Length % 2 != 0) return false;
Dictionary<char, char> dic = new Dictionary<char, char>(){
{'(',')'},
{'{','}'},
{'[',']'}
};
Stack<char> stack = new Stack<char>();
Now when we iterate through our string we can check opening and closing braces just by looking at the keys and values of our dictionary.
We use ‘ContainsKey()’ to process our opening bracket. All opening brackets are keys and all closing brackets are values.
When we iterate through our string we first check whether or not the character is a closing bracket. A closing bracket is a value in our dictionary.
foreach (char c in s) {
if (dic.ContainsValue(c) {
In our previous example (the else if one) we checked for open braces first, then closed braced. This time, with our dictionary, we are checking for closed braces first…and then checking for open braces.
If we find a closed brace, check if the stack is empty. If the stack is empty, this closed brace is an orphan brace. Since the bracket was never opened, just return false.
If the top of the stack is our closed bracket, then pop it off the stack. We have now closed this open / closed parenthesis / bracket pair.
if (dic.ContainsValue(c)) {
if (stack.Count == 0 || stack.Peek() != c) {
return false;
} else {
stack.Pop();
}
}
Now for our open brackets. We don’t have to test for keys, as we already established the value is not a key. Therefore, we push the value to the stack.
else {
stack.Push(dic[c]);
}
Our if / else mess
foreach (char c in s) {
if (c == '(' || c == '[' || c == '{') {
stack.Push(c);
} else if (c == ')' && stack.Count != 0 && stack.Peek() == '(') {
stack.Pop();
} else if (c == ']' && stack.Count != 0 && stack.Peek() == '[') {
stack.Pop();
} else if (c == '}' && stack.Count != 0 && stack.Peek() == '{') {
stack.Pop();
} else {
stack.Push(c);
}
Has become something that still has if / else statements, but is more neat-o.
foreach (char c in s) {
if (dic.ContainsValue(c)) {
if (stack.Count == 0 || stack.Peek() != c) {
return false;
} else {
stack.Pop();
}
}
else {
stack.Push(dic[c]);
}
}
We end our code in the exact same way, by checking whether or not the stack has any values left on it. If the stack is empty we can conclude that every open bracket was closed.
if (stack.Count == 0) {
return true;
} else {
return false;
}
Here is our full dictionary based solution:
static bool IsValid(string s) {
if (s.Length % 2 != 0) return false;
Dictionary<char, char> dic = new Dictionary<char, char>(){
{'(',')'},
{'{','}'},
{'[',']'}
};
Stack<char> stack = new Stack<char>();
foreach (char c in s) {
if (dic.ContainsValue(c)) {
if (stack.Count == 0 || stack.Peek() != c) {
return false;
} else {
stack.Pop();
}
}
else {
stack.Push(dic[c]);
}
}
if (stack.Count == 0) {
return true;
} else {
return false;
}
}
ah, so elegant!