The Valid Parentheses problem on LeetCode is actually pretty fun to solve. Initially, it seems a little tricky, but once you break down the problem into smaller chunks, the solution seems pretty straightforward.
Understanding the problem
The problem basically asks us to determine if a string containing three different kinds of parentheses is valid. For a string to be valid, it must fulfill these three conditions:
This means that something like [()]{} is valid - all open brackets have a corresponding closing bracket and they're closed in the right order, i.e., the opening bracket should come before the corresponding closing bracket, so there's no single open or close bracket left. Plus, the inner brackets should be closed before the outer brackets; otherwise, the string will be invalid.
In contrast, something like ([)] should return false since the open brackets aren't closed in the right order (the closing square bracket should come before the closing round bracket for this to be valid).
Let's go through some more examples so that you really understand what kind of input is valid.
Example #1: (]
This one's clear as day - it's invalid because the closing round bracket and opening square bracket both are missing.
Example #2: (([]){})
This one looks a little tricky, but it's valid since all opening brackets have corresponding closing brackets and the inner brackets are closed before the outer ones. If that sounds confusing, this visual can make things a little clear:
I've numbered the opening brackets with their corresponding closing bracket. As you can see, there's no opening bracket that doesn't have a corresponding closing bracket, and all the opening brackets are closing in order, i.e., the innermost square bracket (numbered 3) is closed first, leaving behind ((){}).
With the square brackets paired, we can remove it from our string to focus on the other brackets. We now have:
Then, we have a pair of round brackets (numbered 2) and a pair of curly brackets (numbered 4). Both of these are in order since their opening bracket is immediately followed by the corresponding closing bracket. With these two pairs complete, we're left with just a single round bracket labeled 1.
And since the round bracket labeled 1 has both opening and closing parentheses in the right order, we'll close that off, too. With everything paired off, we know that our string is valid.
Example #3: {[()]}
Try to work this one out on your own first. This string is also valid, but you should see work out why yourself first if you're still having trouble understanding what makes a string valid or invalid.
If you weren't able to work it out, don't worry. We'll follow the same steps that we did above and number the opening and closing parentheses first.
We can now see that all opening brackets have corresponding closing brackets and the inner ones are closed before the outer ones, making this a valid string.
Putting what we know together
By working through the examples, you might have realized a few things.
The string must be of even length for it to be valid. If it has an odd number of characters, that means it has a single open or closed bracket without its corresponding pair.
The first letter of the string should always be an opening bracket. If it's a closing bracket, that automatically means it's not going to be paired off, making the string invalid.
Expanding on the previous point, the last letter of the string should always be a closing bracket. Otherwise, the string is invalid.
This makes our edge cases for the programs, and let's put this into code first before we actually work on how we can keep track of pairs. In code, these three conditions translate to:
if (s.length % 2 !== 0) {
return false;
}
if(s[0]=== ')'|| s[0]==='}'|| s[0]===']'){
return false
}
if(s[s.length-1]==='(' || s[s.length-1]==='{'||s[s.length-1]==='['){
return false
}
With that out of the way, let's get to the meat of the question. Considering the nature of the question, we can first define our parentheses as key-value pairs where the opening bracket is the key and the closing one is the bracket.
Then, since we first need to match the bracket that we traverse last (for instance, in the case of s={[()]}, we first need to close off the opening round bracket that we reached after passing the other opening brackets), the ideal data structure for us here is a stack (that follows the last-in-first-out paradigm). The purpose of the stack is to keep track of all our open parentheses as we traverse the string.
So let's put both of these things into code:
let parentheses = {
'(': ')',
'{' : '}',
'[': ']'
}
let stack = []
Now, let's traverse through the string. If the character is an open bracket, we'll add it to our stack. If it isn't and is a closing bracket instead, we're going to pop the last opening bracket from the stack and see if that matches the said closing bracket. If it doesn't, that means our string is invalid and we can just return false. If we translate this into code, we get:
for (let i = 0; i < s.length; i++) {
if (s[i] === '[' || s[i] === '{' || s[i] === '(') {
stack.push(s[i]);
} else {
let lastOpening = stack.pop();
if (parentheses[lastOpening] !== s[i]) {
return false;
}
}
}
Now, all that's left to do is check if there's anything left in our stack. If there is, that means our string is invalid but if there isn't and the stack is empty, that means we have a valid string (since we've already taken care of other edge cases). So, in the end, we'll just do this:
return stack.length === 0;
If we put all of the code together, here's how it looks:
let parentheses = {
'(': ')',
'{': '}',
'[': ']'
};
if (s.length % 2 !== 0) {
return false;
}
if(s[0]=== ')'|| s[0]==='}'|| s[0]===']'){
return false
}
if(s[s.length-1]==='(' || s[s.length-1]==='{'||s[s.length-1]==='['){
return false
}
let stack = [];
for (let i = 0; i < s.length; i++) {
if (s[i] === '[' || s[i] === '{' || s[i] === '(') {
stack.push(s[i]);
} else {
let lastOpening = stack.pop();
if (parentheses[lastOpening] !== s[i]) {
return false;
}
}
}
return stack.length === 0;
But if you dry run it, you'll realize that the loop already checks for opening and closing brackets, so we don't explicitly need to check for those. Instead, we can just check if our input is odd and thus invalid, before moving on. So, our refactored code looks like this:
let parentheses = {
'(': ')',
'{': '}',
'[': ']'
};
if (s.length % 2 !== 0) {
return false;
}
let stack = [];
for (let i = 0; i < s.length; i++) {
if (s[i] === '[' || s[i] === '{' || s[i] === '(') {
stack.push(s[i]);
} else {
let lastOpening = stack.pop();
if (parentheses[lastOpening] !== s[i]) {
return false;
}
}
}
return stack.length === 0;
And that's it - you've solved the problem. As always, you can find this solution on my GitHub as well or you can run it directly in OneCompiler. And don't forget to check out my solution to other LeetCode problems!
Solving Leetcode problems is hard enough as it is, and add to that the difficulty of finding an in-depth solution that explains everything, and you find yourself stuck. Some videos are hard to follow, some don't explain the basics, while others leave you with more questions than answers. In this series, I break down Leetcode problems one at a time and walk you through a step-by-step solution. Have a question you can't understand? Send it to me, and I'll explain it in detail. And don't forget to subscribe to my newsletter to get my articles directly into your inbox!