Hey what's up guys Anuj here & welcome to DSA one course & in today's video we will solve a very important question it is a very famous question Parenthesis matching Problem this question is asked very commonly in the interviews it is asked to me several times as well it is a very important question basically, you are given a string in which there can be these 6 characters which are open bracket closing bracket, opening curly braces, closing curly braces opening square bracket & closing square bracket and you have to tell that the expression made by this is it a valid parenthesis matching? how will we check? like here it is matching curly brace is open and then closed both of these brackets also opened & closed so here we will write true here basically, you will be returning True or False this is not matching properly for this opening, we have a closing here for this opening we have this closing but there is no opening for this closing so here it will be false here we have this opening for this closing for this closing, we have this opening for this opening, we have this closing so it will be true here you can see it is okay until here closing & opening for these 3 but here for this opening, this closing bracket is not proper either both of them must have been curly braces or square ones here they are not matching so here also false will return so you can see how simple it is the question is very simple you might be given this question for a one-liner they will ask you to solve the parentheses matching problem after that, you have to think by yourself that what type of parentheses can there be can there be any characters other than parentheses? if there are other characters, how will I handle them? you will counter-question like this ok? they might give you a vague question ok? actually, even I was asked a vague question in an interview and I have to tell them all the constraints to them are you given a string or an array of character what you are given so you have to think about this then you can solve the question it is very easy and with the help of stack you can solve it in O(N) is there any other way? think about it can we solve this without stack? how can we do this? think about it? if you have thought about it then we have a very good option that will be using recursion you can solve it with recursion but there is a recursive stack being used in the recursion so ultimately you are using stack here also ok? let's understand how we can solve this using stack basically, you will be using a stack and as soon as you find a closing bracket for your opening bracket you will remove the opening bracket from the stack this is the funda here let's try for this one how we will do this first we will make a stack ok? this is our stack whenever you find an opening bracket you have to push it in the stack any opening bracket you find first, we found this, so we added it to the stack then we got this so we added that also in the stack then we found this one so we added it too ok? then whenever you find a closing bracket then we have to check if the element on the top and the closing bracket are they matching? means if we have a curly opening so we need a curly closing for it we dont need any other opening so we have to check that we have a curly closing so when we Peek, do we have a curly opening? yes it is a curly opening, so then we will Pop the curly opening we Popped the curly opening then we will move to the next element The next element is also a closing bracket so for a closing element, we have to check for the corresponding opening bracket by Peek so this is our normal closing bracket & & by Peek, we got that this is also normal opening bracket both are matching so we will Pop it then we will move to the next element we will check for it & yes it is also matching so we will pop it as well & now our string is completed so we will check if our stack is also empty? if you string & stack both are done then then it will return True otherwise, we will return False let's take another example let's take this example first we got an opening bracket so we added it to the stack again we had another opening so we added it to the stack then we got a closing bracket so we checked it with the opening bracket they are matching so we will Pop it if they are not matching then we will return False from here itself they matched so we Popped it then we will move to the next element next is closing bracket we Peeked,is this the corresponding matching bracket? yes it is matching, so we will pop it then we will move to the next element next element is the closing one so for that we will Peek we are not getting any element here it means this is the first closing bracket means there was no opening bracket previous to this so we will return False here ok? so that is why it is false here let's try for this one first, we added this curly bracket then we added the next bracket and one by one we added all the opening brackets then we had a closing bracket so we checked if it was matching so we Popped it this bracket was also matching so we removed it too for this also we did the same then we checked for this, but this was not the corresponding bracket ok? for this we needed square opening bracket but we have a curly bracket here so it is not matching so we will return False so this is the logic here basically, we will be using stack & there will be two concepts in the stack first, if it is an opening bracket, so we will Push it in stack if it is a closing bracket, then we will check it with the top one this way we will traverse all our array and at the end when all the array is traversed when the entire array is traversed, then we will check if the stack is empty? so this is going to be our algorithm you must have understood right? let's code this that way you can understand it better so here I have coded the same logic and it is a very simple code it is not tough first, we made a stack stack of character then we will iterate one by one in the sting here is our string here I have two more methods The first one is 'is opening' and the second one is 'is matching' I have made it separately because it was getting messed up here so I wrote them separately here so first we take the first character ok? character at i suppose this is our 1st character ok? then we will check is this an opening character? to check that all you have to do is simply return this if it is among any 3 of these, then it is an opening character so we will return true here so we returned True here because we found an opening bracket here whenever we find an opening bracket, we have to add it to the stack ok? let's make a stack here and as soon as we found an opening character, we added it to the stack we didn't go to else we move to the next character which is this character so we will check is it an opening character? no it is not it means it is a closing bracket first we will check is our stack empty? can you recall, if our stack is empty that means there was no opening bracket before this closing bracket then also we will return false ok? but right now our stack is not empty then we will come to else if & check are they both matching? is the one on the top & the current one this is on top right? and current one is this are they matching? are they corresponding? if yes, then it's ok, but if not return False from here itself for that what I did is made an is matching function here that takes two characters and checks if they are matching how is it checking? that if 'a' is this opening, then 'b' must be this closing or if 'a' is this opening, then 'b' must be this closing or else if 'a' is this opening, then 'b' must be this closing then it will return True, otherwise it will return False in any other condition so basically I made a separate function for is matching here I have updated my code because you can see that the element we are getting by Peek is our opening character and current is the closing one so here 'a' are all our opening characters so I reversed it here so then, we got this one by Peek & our current one is the closing bracket so 'a' is our opening, 'b' is our closing we checked if they are matching that means return True here because this is returning True here this means this condition will not be matching because here we have 'not' so we will go to else & then we will pop so we popped this element basically it is the same logic if you have an opening bracket then add it to the stack if it is a closing bracket first check if the stack is empty or not? if it is not empty then check if they are matching if they are, then it's fine but if they aren't matching then return False from here itself if they are matching then we will Pop the element now our stack is again empty let's move to the next element which is this one this is an opening bracket so we will add it to the stack then we move to the next element that is also an opening bracket so we added it to the stack next element is the closing one it is a closing square bracket so we will go to else is the stack empty? no it isn't are they matching? so these two are matching so we will go to else & Pop it so I popped it then we will move to the next elemet next one is this closing bracketwe we have a closing bracket here but there is no opening bracket then we will check if they are matching? are these element matching? yes they are so we will pop it then again our stack will be empty and we traversed through all the characters after that we are returning s dot is empty if the stack is empty after this then it will return True, otherwise it will return False and as at the end our stack must be empty so from here it will return true here so is parenetheses matching will return True let's see for another example suppose for this example so there is a closing bracket in the beginning so you will go to is opening so it is not an opening bracket, it's a closing one we will check in the closing bracket is the stack empty? Yes it is so it will return False here ok let's take one more example suppose for this example so first we got an opening bracket so we added it to the stack, after that we got the closing bracket like this one so is our stack empty? no it is not so we will check if it is matching so we will get this element by Peek and our current element is this one are they matching? no they won't so this condition will return false here and the rest will also return false so over all we will get False here as they both are not matching they are not matching so it will return False so we will get false here which it should be as these parentheses are not matching ok? so this was a very simple code i hope you must have understood it and you can see the power of stack by now we still have many interesting questions on stack infix, postfix & prefix these expressions are also solved in stack we will have a look at that in the upcoming videos stay tuned & you can find some questions in the description which you can solve for practice on that note see you in the next video if you liked this video then do like & subscribe see you in the next video.
Bye Bye..