LeetCode 20. Valid Parentheses Solution Explained - Java
HTML-код
- Опубликовано: 11 сен 2024
- The Best Place To Learn Anything Coding Related - bit.ly/3MFZLIZ
Join my free exclusive community built to empower programmers! - www.skool.com/...
Preparing For Your Coding Interviews? Use These Resources
--------------------
(My Course) Data Structures & Algorithms for Coding Interviews - thedailybyte.d...
AlgoCademy - algocademy.com...
Daily Coding Interview Questions - bit.ly/3xw1Sqz
10% Off Of The Best Web Hosting! - hostinger.com/...
Follow Me on X/Twitter - x.com/nickwhit...
Follow My Instagram - / nickwwhite
Other Social Media
----------------------------------------------
Discord - / discord
Twitch - / nickwhitettv
TikTok - / nickwhitetiktok
LinkedIn - / nicholas-w-white
Show Support
------------------------------------------------------------------------------
Patreon - / nick_white
PayPal - paypal.me/nick....
Become A Member - / @nickwhite
#coding #programming #softwareengineering
![[DOKKAN BATTLE] Worldwide Campaign Announcement Video Part 2!](http://i.ytimg.com/vi/JpT5Voak6WA/mqdefault.jpg)
For cases like "( [ } } ] )" we should add a else block to return false. Code Below:
class Solution {
public boolean isValid(String s) {
if(s.length() % 2 != 0){
return false; //base case, all elements need to have a pair. So total count should be even
}
Stack stack = new Stack();
for(char c: s.toCharArray()){
if(c == '(' || c == '[' || c == '{'){ //push all opening braces to stack & compare them with closed ones later.
stack.push(c);
}
else if(c == ')' && !stack.isEmpty() && stack.peek() == '(' ){ //if top element in stack is ( and given element is ) then remove that pair.
stack.pop();
}
else if(c == ']' && !stack.isEmpty() && stack.peek() == '[') {
stack.pop();
}
else if(c == '}' && !stack.isEmpty() && stack.peek() == '{') {
stack.pop();
}
else{
return false; //when cases like }}, )), ([}}]) this will return false
} //stack.push(c)
}
return stack.isEmpty(); //when every pair is removed then stack becomes empty & it is true. else false
}
}
yes, you are absolutely correct !!!
thanks man. i was looking for this
great clarification, thanks!
Noticed that as well.
Also in case if the string starts with a closing parentes the "else return false" statement would catch that
Your code does not work if the testcase is ")}" or any testcases which contain only closing brackets because of your If-Else Statements. It would be better if you add the command: " else stack.push(c); ". Thank you for your contribution!
yes, helped me
Thank you! this is the last missing logic
yes! thank you :)
Thanks for this fix. Mine was failing on " ( [ } } ] ) ".
Because the stack was not empty, it wasn't doing anything to register the invalid closing parenth
added else return false
This will give the wrong answer for "))". There should be an else: return False
Yes, its surprising the code passed the test. When I run it on idea, it gives me the wrong answer with"()]]".
@@yuchenhu483 add else stack.push(c) after last else if
yep remember to add "else return false;" on your last line of the for loop
@@KM-zd6dq yes I did also faced the same issue
@@meezanshaikh6692 Thanks makes sense
This will fail for a case like "( [ } } ] )". We need to add one else statement where we push the character into the stack.
I was wondering the same thing, this code needs a last `else {stack.push(c)}` but how does this gets passed in leetcode? was this testcase added later?
@@youshamahmood3183 not working in my leet code
class Solution {
public boolean isValid(String s) {
if (s.length()%2!=0) return false;
Stack stack=new Stack();
for(char c:s.toCharArray()){
if(c=='('|| c=='{'|| c=='['){
stack.push(c);
}else if (c==')' && !stack.isEmpty() && stack.peek()=='('){
stack.pop();
}else if(c=='}' && !stack.isEmpty() && stack.peek()=='{'){
stack.pop();
}else if(c==']' && !stack.isEmpty() && stack.peek()=='['){
stack.pop();
}
else return false;
}
return stack.isEmpty();
}
}
Hey... I don't know if it was a bug in leetcode, but that code of yours doesn't work anymore. In order to make it work, you need to add a final 'else return false' at the end.
That's becuase that code doesn't handle situtions like this " [ ) ) ]". The double closing parantheses get completely ignored as there's no case that handles them, and they shouldn't get ignored.
add else stack.push(c) after last else if
Yes you are correct
not being accepted on leetcode
Thanks Nick .Great explanation.This solution is failing for few test cases.example - "([}}])".We need to push to stack on line number 15.
For better runtime, return false on line 15
Good video, however if all the input is closing brackets with even quantity, it won't pass the test. for example the input is "}}", my suggestion is we can put else branch at the end where we basically just return false. since we know that the first input will be a closing bracket.
yeah i think you are right. I have the same question
I think leetcode doesn't account these test cases.. they should have accounted for these
Your videos are awesome, great explanation. I Have a few questions not related to this video but for interview preparation.
I already did about 70 leet code but after a month when I look at the same problem I solved it I don't remember which algorithm I used and it takes me 30 mins or one hour to solve it again. Is this normal? Can you please guide me in these 3 questions:
1. When were you looking at the correct solution -- before you began the problem when you got stuck, only after struggling to solve it yourself? How long until you would look at the solution, typically?
2. What would you do after you'd not solved the problem, but looked at the answer?
3. What would you do after you did solve a problem?
I appreciate all you hard work and help us.
Uhh, this doesn't work for test case: "([}}])"
simply add this condition after else if conditions
else {
return false ;
}
solution doesn't work for "([}}])" not currently accepted by leetcode
Same here can u please help
@@Ram-vg5fu Just add on an else statement at the end of all the else if's. You can put a counter that increments if any case goes there. Then have a check to see if the counter is greater than 0, if it is return false. Boom. Solved.
Hi @Jenna,
Below code works perfectly for leetcode.
static boolean validateByMap(String s){
HashMap map = new HashMap();
map.put('(', ')');
map.put('[', ']');
map.put('{', '}');
Stack stack = new Stack();
for (int i = 0; i < s.length(); i++) {
char curr = s.charAt(i);
if (map.keySet().contains(curr)) {
stack.push(curr);
} else if (map.values().contains(curr)) {
if (!stack.empty() && map.get(stack.peek()) == curr) {
stack.pop();
} else {
return false;
}
}
}
return stack.empty();
}
add else{ return false;} after all else if statements
Use a hash table instead of if else's, way cleaner. The core of the algo is still the same, the pushes and the pops have to match up
Tried to solve it myself without stack. Took an hour or two, runtime 1ms, memory 37 MB. Code length much longer than this. Watched video, reproducesd the solution on LeetCode. Got the same 1ms and 37 MB, but code is three times shorter, which is a big win.
Can you tell me the solution without stack if you don't mind and thank you
Good explanation, Thank you! I've a question, what if many brackets are there, using if-else or switch checking the closing brackets many times is good? And, another question is that instead of if-else/switch, how abt using hashmap for checking opening brackets the same with atop element in the stack?
As others mentioned, great video but the code does not consider the case if the input is all closing parentheses. One possible fix is adding an additional 'else if' right after the if statement that checks if the char is a closing parenthesis and the stack is empty, if both satisfy it can return False.
worked
Good explanation but sadly this code doesn't work for the case " ( [ } } ] ) " , requires an extra else block to return false.
if this is the string given "{ [ ] } ]" this solution gives wrong answer. Thank you for your contribution!
You have missed one last else block for some cases like "( [ } } ] )"
your code fails on "([}}])" test case. I am also using leetcode may they now added some more test cases.
why did you include CONDITION TO CHECK IF STACK IS EMPTY OR NOT?? BCOZ IF IT HAD BEEN EMPTY STACK.PEEK WOULD NOT HAVE TAKEN PLACE !! SO WY SPECIFY IT??
If it runs stack.peek() when stack is empty it throws an exception, so you need to check first.
It seems to be that your code does not consider input like this ")" ? ?
Thanks Nick for the explanation ! Can we use map instead of multiple if else conditions ?
Yes you can.
However, a map would be O(n) space complexity as opposed to the else if which is O(1)
if we take test case as "}])"what will it return ?
What does stack.peek() return?
How does it run through the case "{[]}"?
Fun video!! Great job :D
ChocolateAndMath stack.peek() returns the value at the top of the stack. For ‘{[]}’
It pushes { and [ to the stack. Then it gets to the ] conditional. Since the top of the stack at the moment is its corresponding opening bracket [, it removes the opening bracket. The only bracket remaining in stack is { now. Then the next iteration, c is } and checks the top of stack, it matches { and pops it off. Now the Stack is empty voila
Thank you, Nick, for explaining!
Add the below as well
else return false; // To handle (})
unreal !!!
Oh my...
Hey Nick, really awesome explanation. I hope you can keep doing these videos
your soln is giving "bad operand types for binary operator '||' .in line 7
I remember doing this and got stuck why is it wrong.
The genius in me realized about 30 mins later that the open and close parenthesis are not palindromes...
What would be the time complexity of this solution?
left ear enjoyed this
Your code is wrong for cases such as '}}"
Great explanation
Thanks Nick
Thank you very much for all your videos..for pattern "([}}])" this code does not work.. add "else false;" condition to it.. this is basically you not popping anything from stack even if you get closing bracket.. so we can stop here and return false..
line 3 wont work if input = '((()'
you are the best thanks!
confusion.CLEARED(); THANK YOU!
Great and clear solution! Thanks! Although it passes Leetcode, I think we should add "else return false" after the last "else if". Since (])] should be false, however the code in the video would not recognize that it is false.
else stack.push(c) will work too
@@meezanshaikh6692 it will not work if first element is any closing bracket
@@nileshpatil3710 yes. I was a bad coder last year 🤐
there should be another condition for returning the false, as for the case '([ {{ ])' , the code pushes ([ to the stack and checks if } is present at the peek of stack and does not pops then again checks for another } and verifies if corresponding { is also not there in the stack and does not pops the element which in both of the above cases should return false, and finally verifies ] and ) and pops simultaneously verifying them present at the peek and returns true for stack to be empty, which is a *WRONG* solution either a condition to be added to return false if any of the above condition is not satisfied!! """ else return false; """ or either we can push that element to the stack """ else stack.push(c); """
time complexity?
thanks for good explanation :D
Looks like LC updated test cases.
Comment Line #3. Added below after line #15. With this we can extend this test case IDE design problem. For ex -
Test case - {print (hello World)} - PASS
- 3 //if (s.length() % 2 !=0) return false;
+16 else if (c =='(' || c =='{' || c=='[' || c =='}' || c==')' || c ==']') {
+17 return false;
+18 }
return false in else condition.
if we find c == ')' while the stack is empty, what will happen?
Or, when we find c == ')' and stack is empty, but the peek() is not '(', what do we do?
Okay, think i know the answer, just add else return false at the end of else if conditions. Thanks for the video!
will this code work for ( ] )
Please correct the mistake....
Thank you!
🤩🤩🤩🤩🤩🤩🤩🤩🤩🤩🤩 Thank you so much
Bro
Thanks man :)
left ear left the chat.
right ear never entered the chat.
Tnx Man !
This solution fails 4 test cases
This code does not works for the single string "]" or "}" or ")"
I just did it the same way just forgot to pop in the last. Damn it.
("(abc())") i got this in my tests so using stack wont work any ideas how to go about this one?
Brilliant
class Solution {
public boolean isValid(String s) {
if(s== null)
return false;
int length = s.length();
if(length %2 ==1)
return false;
Stack stack = new Stack();
for(int i=0; i< s.length(); i++)
{
boolean check = false;
if(s.charAt(i)=='(' || s.charAt(i)=='{' || s.charAt(i)=='[')
{
stack.push(s.charAt(i));
check = true;
}
// Do not peek empty stack to avoid exception
if(s.charAt(i)==')' && !stack.isEmpty() && stack.peek()=='(')
{
stack.pop();
check = true;
}
if(s.charAt(i)=='}' && !stack.isEmpty() && stack.peek()=='{')
{
stack.pop();
check = true;
}
if(s.charAt(i)==']' && !stack.isEmpty() && stack.peek()=='[')
{
stack.pop();
check = true;
}
if(check == false)
return false;
}
return stack.isEmpty();
}
}
wrong answer
add else stack.push(c) after last else if
add else{ return false;}
else { return false;}
GREAT VIEO.
correction
class Solution {
public boolean isValid(String s) {
if(s.length() % 2 != 0){
return false;
}
Stack stack = new Stack();
for(char c : s.toCharArray()){
if(c == '(' || c == '[' || c == '{'){
stack.push(c);
} else if(c == ')' && !stack.isEmpty() && stack.peek() == '('){
stack.pop();
} else if(c == '}' && !stack.isEmpty() && stack.peek() == '{'){
stack.pop();
} else if(c == ']' && !stack.isEmpty() && stack.peek() == '['){
stack.pop();
} else{
stack.push(c);
}
}
return stack.isEmpty();
}
}
Get your code
I'd love to see this problem solved using recursion
No
this is wrong
he has zero knowledge. just copies solutions.
great explanation
great explanation