Valid Parenthesis - Crack Coding Interviews

All right, this is another classic question. Valid parentheses. Given a string s containing just the characters, these parentheses determine if the input string is valid. And it is valid if you satisfy these two conditions. The open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. So let's put this in perspective. If we have an input string s, you have a pair of parentheses followed by square brackets, and then you have curly braces. That means this is valid. But if we have opening parentheses, but we have a closing square bracket, and it's not closed by the closing parentheses, that means it's not valid. So another example would be, you could have a, for example, you have a parentheses, but embedded you have a square brackets. And then you have, for example, a pair of curly braces inside. So that's another valid parentheses. Or you could have the curly braces outside. So something like this will also be. So it has to be, the same parentheses has to be closed by the same type of parentheses. All right. So let's look at how we tackle this problem. We may find a pattern here. So if we, for example, every time we encounter an opening parentheses, so we're going to use a stack. We're going to use a stack to put in its corresponding closing parentheses. What does that mean by that? So let's go one by one. So we have opening parentheses, and then in the stack, we're going to put a closing parentheses. So we have a closing square bracket. We're going to say, put its counterpart here. But if we have a closing parentheses or closing square brackets, we're going to keep it the same in the stack. And then every time we have a closing brackets, that means if it's not a opening parentheses, we're going to pop that from the stack. So let's just complete this first. So if it's the next one, it will be a closing parentheses. The next one is an opening curly braces. So we're going to put a closing curly braces. And then last one here. So first, we put a closing parentheses and then a closing square brackets. And then the next one is a closing brackets. Then we're going to pop this one. Take what's on the top of the stack. If it's same, then we're going to pop. So after we pop, then we are left with a closing parentheses. Then the next character will be exactly also a closing parentheses. So we're going to pop that as well. Then the stack will be empty. And the last but not least, we have a curly braces. And then we're going to put in the stack a closing curly braces because this is opening one. And then lastly, we have a closing curly braces. Then we're going to pop. Then eventually, if it's valid, the stack is going to be empty. So let's look at a non-valid example. So if I put this closing brackets into here. So what's going to happen is, so first you have a closing parentheses. And next, you keep this as a closing square bracket. The next, because it's an opening square bracket, so we're not going to pop from the stack. So eventually, we're going to have another one on the stack. And the next, we have a closing parentheses. And then we're going to have to pop that. But then we found out that if we pop the very top element from the stack, it's not equal to the corresponding closing parentheses. That means it's not a valid parentheses string. So it sounds a little bit confusing, but let's put it in perspective by code. So like we said, first, we're going to define a stack of characters. All right, we're just going to call this stack is equal to new stack. So apparently, we have to do a loop. So for each character, let's call it c in this string. So we're going to say two char string is going to convert the string into a character. If c is equal to, remember, notice I'm using a single quotation for character. If it's an opening parentheses, I'm going to stack.push a closing parentheses, right? So closing parentheses, as I might call here, should be opening parentheses. And then else, if we copy this over, so else if it's equal to a opening square bracket, I'm going to push a closing square bracket, right? So likewise, opening curly braces, curly brace, and then closing curly brace. There we go. Last but definitely not least, this is the default case. If we reach the end of the stack, actually, let's say if stack is not empty, or if stack.pop, so if it's not any of these, so if it's a valid parentheses, it could be any of the closing counterparts, right? So if it's any of the closing counterpart, we're going to pop the top element from the stack, right? And say if it equals c or not. And if it's not equal to c, and remember, this one is going to return the element from the top of the stack. But in the meantime, it's going to remove the element. So we don't have to have, we can just put this within the if statement, the condition part. So if that's the case, if the top of the stack is not equal to the current character, and by the time we reach here, because we already passed these conditions, that means this character has to be one of these closing cases, right? Otherwise, it will fall into any of these categories. So if the top of the stack is not equal to the character, that means it's not a parentheses. Or if we reach the end of the stack, but the stack is not empty, remember, in order for it to be valid, at the end of the process, the stack has to be empty. If it's not empty, that means it's not valid. So if any of these conditions are true, so we're going to return false, right? And otherwise, we're going to return true. So that means we loop through everything, and this stack becomes empty. And for every step of the way, the top of the stack is equal to the corresponding closing case, right? Let's run this algorithm. Oh, we have to put additional parentheses here to wrap this around, so that it's not confusing if it's not equal to the character. Okay, I think I was missing the closing parentheses for the last if statement. And let's submit the algorithm again. Okay. All right. So here, I could say, is not equal to the character, right? So and then, oh, here, it shouldn't be not empty, but empty. So why that's the case? So just think about, once we reach this point, that means we're still in the character array. So if we're still in the character array, but the stack is already empty, that means we have parentheses that cannot be matched, because the stack is already empty, and it's unbalanced. It's not even an even number of characters in the array. So an example would have two opening square brackets, but we only have one closing square bracket, right? So that will break the balance. So because the stack is going to be, so we have a close, close, and the next one will be close, and then that means we're going to pop the previous one, and then eventually this is the end of the stack, right? So if it's the end of the stack, and if it's still not empty, that means it's not going to be a valid parentheses. And last but not least, we're not going to return true. So we're going to return if the stack is empty or not, right? So let's see. Let's submit the program. There we go, right? So hopefully this makes sense. And this is another classic example of using a stack to detect every time you have problems like this, you have a pair of characters or things like that, you want to see if it's a balance or not, you can apply the same logic.