Parenthesis Checker | Valid Parentheses Leetcode | Balanced Parentheses Hackerrank | DSAOne #43
Parenthesis Checker | Valid Parentheses Leetcode | Balanced Parentheses Hackerrank | DSAOne #43
Hey guys, In this video, We’re going to solve another very famous Interview Problem called - Parentheses Matching Problem.
code: https://www.geeksforgeeks.org/check-f…
Practice questions: https://www.interviewbit.com/courses/…
🥳 Join our Telegram Community:
Telegram channel: https://telegram.me/realanujbhaiya
Telegram group: https://telegram.me/dsa_one
🚀 Follow me on:
Instagram: https://www.instagram.com/Anuj.Kumar…
Linkedin: https://www.linkedin.com/in/sharma-ku…
Twitter: https://twitter.com/realanujbhaiya
💸 Use coupon code ANUJBHAIYA on GeeksforGeeks to avail discounts on courses!
📚 Complete DSA Playlist: • DSA-One Course - The Complete Data St…
Complete Android Development Playlist: • Android Development Tutorial for Begi…
Hashtags:
#anujbhaiya #dsaone
Ignore these tags:
parenthesis checker
valid parentheses
anuj bhaiya
valid parentheses leetcode
valid parentheses leetcode java
balanced parentheses hackerrank solution
balanced parenthesis
balanced paranthesis
balanced parentheses
longest valid parentheses
parentheses
valid parenthesis
valid paranthesis
balanced brackets
generate parentheses leetcode
minimum swaps for bracket balancing
sherlock and parentheses solution
stack in java
valid substring
20. valid parentheses
stack dsa
balanced parentheses problem
dsa in java
generate parentheses
minimum remove to make valid parentheses
remove invalid parentheses
parentheses and brackets
stack
stack in dsa
stack questions
stacks in java
valid parentheses leetcode c++
balanced brackets hackerrank solution
create a program to return array of all balanced parenthesis.
dense bracket sequence solution
leetcode valid parentheses
stack data structure
stack in data structure
)
anuj bhaiya dsa
anuj bhaiya java
apna college
boolean parenthesization
check for a matching contact in your org
create a program to return array of all balanced parenthesis
expression contains redundant bracket or not
generate parenthesis
leetcode 20
parenthesis
stack java
stack problems
time complexity analysis
valid parentheses java
valid parentheses leetcode python
2116. check if a parentheses string can be valid
Content
0 -> Hey what's up guys Anuj here &
0.986 -> welcome to DSA one course &
2.26 -> in today's video we will solve a very important question
4.585 -> it is a very famous question
5.522 -> Parenthesis matching Problem
7.689 -> this question is asked very commonly in the interviews
10.368 -> it is asked to me several times as well
11.628 -> it is a very important question
13.18 -> basically, you are given a string in which
14.605 -> there can be these 6 characters
16.903 -> which are open bracket
18.216 -> closing bracket, opening curly braces, closing curly braces
20.944 -> opening square bracket & closing square bracket
23.441 -> and you have to tell that the expression made by this
25.994 -> is it a valid parenthesis matching?
28.757 -> how will we check?
29.648 -> like here it is matching
30.786 -> curly brace is open
31.993 -> and then closed
32.619 -> both of these brackets also opened & closed
35.184 -> so here we will write true
36.631 -> here basically, you will be returning True or False
38.669 -> this is not matching properly
40.833 -> for this opening, we have a closing here
42.659 -> for this opening we have this closing but
44.081 -> there is no opening for this closing
46.511 -> so here it will be false
47.658 -> here we have this opening for this closing
50.25 -> for this closing, we have this opening
51.162 -> for this opening, we have this closing
52.219 -> so it will be true
53.046 -> here you can see it is okay until here
55.113 -> closing & opening for these 3
56.634 -> but here for this opening, this closing bracket is not proper
59.732 -> either both of them must have been curly braces or square ones
63.866 -> here they are not matching so
64.977 -> here also false will return
66.435 -> so you can see how simple it is
68.686 -> the question is very simple
69.674 -> you might be given this question for a one-liner
72.932 -> they will ask you to solve the parentheses matching problem
75.237 -> after that, you have to think by yourself
77.021 -> that what type of parentheses can there be
78.88 -> can there be any characters other than parentheses?
81.407 -> if there are other characters, how will I handle them?
83.542 -> you will counter-question like this ok?
85.046 -> they might give you a vague question ok?
86.159 -> actually, even I was asked a vague question in an interview
89.147 -> and I have to tell them all the constraints to them
91.863 -> are you given a string or an array of character
94.705 -> what you are given
95.889 -> so you have to think about this
97.493 -> then you can solve the question
98.895 -> it is very easy
99.734 -> and with the help of stack you can solve it in O(N)
102.244 -> is there any other way?
103.687 -> think about it
104.356 -> can we solve this without stack?
106.666 -> how can we do this? think about it?
107.534 -> if you have thought about it
109.936 -> then we have a very good option
111.603 -> that will be using recursion
113.35 -> you can solve it with recursion but
115.792 -> there is a recursive stack being used in the recursion
118.654 -> so ultimately you are using stack here also ok?
121.216 -> let's understand how we can solve this using stack
123.351 -> basically, you will be using a stack and
125.901 -> as soon as you find a closing bracket for your opening bracket
128.726 -> you will remove the opening bracket from the stack
132.097 -> this is the funda here
132.906 -> let's try for this one how we will do this
135.317 -> first we will make a stack ok?
137.224 -> this is our stack
138.472 -> whenever you find an opening bracket
140.411 -> you have to push it in the stack
141.867 -> any opening bracket you find
143.704 -> first, we found this, so we added it to the stack
145.7 -> then we got this so we added that also in the stack
147.927 -> then we found this one so we added it too
150.429 -> ok?
151.063 -> then whenever you find a closing bracket
153.359 -> then we have to check if
154.416 -> the element on the top
156.378 -> and the closing bracket
158.073 -> are they matching?
159.421 -> means if we have a curly opening so we need a curly closing for it
164.064 -> we dont need any other opening
165.836 -> so we have to check
166.881 -> that we have a curly closing
168.868 -> so when we Peek, do we have a curly opening?
170.897 -> yes it is a curly opening, so then
172.872 -> we will Pop the curly opening
176.219 -> we Popped the curly opening
177.635 -> then we will move to the next element
179.357 -> The next element is also a closing bracket
181.724 -> so for a closing element, we have to check for
184.297 -> the corresponding opening bracket by Peek
188.875 -> so this is our normal closing bracket &
191.409 -> & by Peek, we got that this is also normal opening bracket
195.495 -> both are matching so we will Pop it
197.619 -> then we will move to the next element
198.943 -> we will check for it & yes it is also matching so
201.984 -> we will pop it as well &
203.848 -> now our string is completed so
205.781 -> we will check if our stack is also empty?
208.272 -> if you string & stack both are done then
210.722 -> then it will return True
212.469 -> otherwise, we will return False
214.954 -> let's take another example
216.397 -> let's take this example
217.495 -> first we got an opening bracket so we added it to the stack
221.236 -> again we had another opening so we added it to the stack
223.669 -> then we got a closing bracket so we checked it with the opening bracket
226.636 -> they are matching so we will Pop it
229.073 -> if they are not matching then we will return False from here itself
230.892 -> they matched so we Popped it
232.844 -> then we will move to the next element
233.578 -> next is closing bracket
234.814 -> we Peeked,is this the corresponding matching bracket?
237.409 -> yes it is matching, so we will pop it
241.108 -> then we will move to the next element
242.537 -> next element is the closing one
243.682 -> so for that we will Peek
245.797 -> we are not getting any element here
247.281 -> it means this is the first closing bracket
249.832 -> means there was no opening bracket previous to this
252.142 -> so we will return False here ok?
254.215 -> so that is why it is false here
255.934 -> let's try for this one
257.445 -> first, we added this curly bracket
259.737 -> then we added the next bracket
261.442 -> and one by one we added all the opening brackets
263.327 -> then we had a closing bracket so we checked if it was matching
266.871 -> so we Popped it
267.657 -> this bracket was also matching so we removed it too
270.809 -> for this also we did the same
273.781 -> then we checked for this, but this was not the corresponding bracket ok?
277.876 -> for this we needed square opening bracket
281.352 -> but we have a curly bracket here
283.919 -> so it is not matching so we will return False
287.445 -> so this is the logic here
289.164 -> basically, we will be using stack
291.152 -> & there will be two concepts in the stack
293.719 -> first, if it is an opening bracket,
296.376 -> so we will Push it in stack
297.815 -> if it is a closing bracket,
299.312 -> then we will check it with the top one
300.871 -> this way we will traverse all our array
303.066 -> and at the end when all the array is traversed
305.395 -> when the entire array is traversed,
307.573 -> then we will check if the stack is empty?
310.205 -> so this is going to be our algorithm
311.994 -> you must have understood right?
313.039 -> let's code this
314.394 -> that way you can understand it better
316.76 -> so here I have coded the same logic
318.722 -> and it is a very simple code
320.013 -> it is not tough
320.894 -> first, we made a stack
322.396 -> stack of character
324.031 -> then we will iterate one by one in the sting
326.315 -> here is our string
327.259 -> here I have two more methods
328.779 -> The first one is 'is opening'
330.138 -> and the second one is 'is matching'
331.24 -> I have made it separately
332.102 -> because it was getting messed up here
334.099 -> so I wrote them separately here
335.839 -> so first we take the first character ok?
337.903 -> character at i
339.036 -> suppose this is our 1st character ok?
341.013 -> then we will check is this an opening character?
343.283 -> to check that all you have to do is
344.905 -> simply return this
346.535 -> if it is among any 3 of these, then it is an opening character
349.134 -> so we will return true here
352.508 -> so we returned True here
354.124 -> because we found an opening bracket here
355.728 -> whenever we find an opening bracket,
356.764 -> we have to add it to the stack ok?
358.637 -> let's make a stack here
360.838 -> and as soon as we found an opening character,
362.114 -> we added it to the stack
363.594 -> we didn't go to else
364.829 -> we move to the next character
366.158 -> which is this character
367.547 -> so we will check is it an opening character?
369.646 -> no it is not
370.404 -> it means it is a closing bracket
372.141 -> first we will check is our stack empty?
374.452 -> can you recall, if our stack is empty that means
376.322 -> there was no opening bracket before this closing bracket
379.143 -> then also we will return false ok?
380.923 -> but right now our stack is not empty
382.957 -> then we will come to else if & check
384.302 -> are they both matching?
386.107 -> is the one on the top & the current one
388.529 -> this is on top right?
389.406 -> and current one is this
390.597 -> are they matching?
391.353 -> are they corresponding?
392.414 -> if yes, then it's ok, but if not
393.643 -> return False from here itself
394.729 -> for that what I did is
395.7 -> made an is matching function here
397.123 -> that takes two characters
399.119 -> and checks if they are matching
400.825 -> how is it checking?
401.589 -> that if 'a' is this opening, then 'b' must be this closing
404.206 -> or if 'a' is this opening, then 'b' must be this closing
407.775 -> or else if 'a' is this opening, then 'b' must be this closing
410.223 -> then it will return True, otherwise
411.51 -> it will return False in any other condition
414.422 -> so basically I made a separate function for is matching
416.409 -> here I have updated my code
417.783 -> because you can see that the element we are getting by Peek
419.807 -> is our opening character
421.219 -> and current is the closing one
422.019 -> so here 'a' are all our opening characters
424.776 -> so I reversed it here
426.389 -> so then, we got this one by Peek &
428.938 -> our current one is the closing bracket so
430.746 -> 'a' is our opening, 'b' is our closing
432.81 -> we checked if they are matching
433.895 -> that means return True here
435.608 -> because this is returning True here
437.582 -> this means this condition will not be matching
440.426 -> because here we have 'not'
442.041 -> so we will go to else &
443.747 -> then we will pop
444.962 -> so we popped this element
447.076 -> basically it is the same logic
448.338 -> if you have an opening bracket then
449.595 -> add it to the stack
450.543 -> if it is a closing bracket
451.579 -> first check if the stack is empty or not?
453.433 -> if it is not empty then check
454.946 -> if they are matching
455.979 -> if they are, then it's fine
457.138 -> but if they aren't matching then return False from here itself
458.713 -> if they are matching then we will Pop the element
461.614 -> now our stack is again empty
463.518 -> let's move to the next element which is this one
465.325 -> this is an opening bracket
466.373 -> so we will add it to the stack
469.065 -> then we move to the next element
470.447 -> that is also an opening bracket
471.814 -> so we added it to the stack
473.301 -> next element is the closing one
475.005 -> it is a closing square bracket
477.471 -> so we will go to else
478.786 -> is the stack empty? no it isn't
479.843 -> are they matching?
480.729 -> so these two are matching
483.626 -> so we will go to else & Pop it
487.496 -> so I popped it
488.513 -> then we will move to the next elemet
489.776 -> next one is this closing bracketwe
492.243 -> we have a closing bracket here but there is no opening bracket
493.821 -> then we will check if they are matching?
495.788 -> are these element matching? yes they are
497.954 -> so we will pop it
499.085 -> then again our stack will be empty
500.28 -> and we traversed through all the characters
502.263 -> after that we are returning s dot is empty
505.596 -> if the stack is empty after this then
507.229 -> it will return True, otherwise it will return False
509.634 -> and as at the end our stack must be empty
511.608 -> so from here it will return true here
514.257 -> so is parenetheses matching will return True
517.383 -> let's see for another example
519.283 -> suppose for this example
520.926 -> so there is a closing bracket in the beginning
522.512 -> so you will go to is opening
524.604 -> so it is not an opening bracket, it's a closing one
526.486 -> we will check in the closing bracket
527.459 -> is the stack empty? Yes it is
529.314 -> so it will return False here ok
531.276 -> let's take one more example
533.406 -> suppose for this example
535.895 -> so first we got an opening bracket
538.728 -> so we added it to the stack, after that
539.769 -> we got the closing bracket like this one
541.111 -> so is our stack empty? no it is not
543.231 -> so we will check if it is matching
544.567 -> so we will get this element by Peek
546.87 -> and our current element is this one
548.621 -> are they matching? no they won't
550.966 -> so this condition will return false here
552.458 -> and the rest will also return false
554.989 -> so over all we will get False here
556.722 -> as they both are not matching
558.118 -> they are not matching so it will return False
560.55 -> so we will get false here
562.05 -> which it should be
562.776 -> as these parentheses are not matching
565.05 -> ok?
565.825 -> so this was a very simple code
567.07 -> i hope you must have understood it
568.013 -> and you can see the power of stack by now
570.597 -> we still have many interesting questions on stack
574.191 -> infix, postfix & prefix
575.7 -> these expressions are also solved in stack
577.579 -> we will have a look at that in the upcoming videos
579.472 -> stay tuned & you can find some questions in the description
582.898 -> which you can solve for practice
584.658 -> on that note see you in the next video
586.548 -> if you liked this video then do like & subscribe
589.124 -> see you in the next video. Bye Bye.
Source: https://www.youtube.com/watch?v=aKTGpBeOeZg