Thanks. Also you can add a check on top if the size of the string is odd. And if its is, return false before checking anything else. Because that's just O(1) check assuring that anything can be closed at all (you can't close each bracket if the sum of chars is not even).
@@adarshsasidharan254 This is definitely a smart idea although remember some variations of this problem asked contain random chars other than brackets. This check would obv give a wrong result then.
A base case can be added at the beginning that checks if the string length is odd and if so return false. This can optimize the time to O(1) if the string is odd (since there will be one bracket without a pair).
Man I got asked this question today and totally bombed it. I had a recursive implementation that kind of worked but missed a bunch of cases. Well back to learning it is. Your channel and experience is a truly godsent.
luv that u explain the detail to all levels, like why a stack is helpful here & you lead listeners to suspect such a thing themselves ... super kind way, directly helpful 2 getting ppl into the mindset of solving these problems. mad thx
I was in the ball park with the hashmap, the stack, and the general idea, but handling the edge cases stumped me. Streamlined your code on my end just to make sure I understand it, thanks!
Hey, just want to let you know that I absulutely LOVE neetcode and all your videos. I'm a huge fan! Also, the code that you have on neetcode for this problem is a little different. I like the one from this video a lot better!
i also used the stack data structure but use the if and else conditions therefor i came here to see more optimal and easy way and i got what i expect from your channel, thank you so much.
Hey thanks for the video. I fought with this problem quite a lot. Had not heard about stacks before. I did not find this problem an easy one to be honest. Thanks for the explanation!
Your explanation was perfect, yet I'm afraid I didn't understand that I wasn't able to solve this problem because I didn't know how to work with stack data structures. Good job my friend!
Hi Sir, thank you for the amazing roadmap! I have a suggestion: could you clone the same roadmaop and avoid mentioning the category of each problem? Knowing the category often gives away the approach, which takes away the challenge. For example, when I saw that this problem labeled "stack" I solved it quickly but missed the chance to think critically. Removing the categories could make the learning process even more effective. Thanks again for all your efforts! 🌹
Agreed, the trick is actually hard to pick so anyone who can solve most likely knows the trick or it would be hard. The code is easy though but not the strategy.
You did it way smarter than what I tried to. I made a hash table but I did one where the opening parentheses are they keys not the vales, the other way way is much simplier.
How is it any different? def isValid(s: str) -> bool: char_map = {"(": ")", "[": "]", "{": "}"} stack = deque() for c in s: if c in list(char_map.keys()): stack.append(c) else: if not stack or char_map[stack.pop()] != c: return False return not stack
The fact that this is easy is a little discouraging considering I fumbled around with it for several hours since I didn't know what a stack is. Glad to be able to learn this now though!
You can slightly simplify this using only stack.pop() instead of stack[-1] and then stack.pop() as stack.pop() also returns the value you wanted to check, if its False we're exiting the function, if its True then we both did the verification of the value AND we performed the stack.pop() that we will need e.g. for char in s: if char in close_to_open: if stack.pop() != close_to_open[char]: return False else: stack.append(char)
8:30 I think we dont need to necessarily check if the first char is closing parentheses then is not valid, we can 'return not stack' and get the case covered
True, but it helps when he writes it out in dumb speech like that. In an interview it would probably also help to know that you can write it out both ways.
@@pauljones9150 I interviewed many candidates at Google; if someone wrote that on the whiteboard it'd be a red flag. No one should be writing production code this way and such unnecessary code would be flagged at review time.
i started from working around Dijkstra's Two Stack algorithm which uses similar logic and managed to do it without using hash map, but it required from me handling popping from an empty stack and also resulted in longer and dirtier (although simple to understand) code.
this one took me a good 30 minutes. all I knew going into it was that it utilized the stack data structure. I was able to come up with the logic for it by thinking about how I would solve it just in my head if someone presented me with a sequence of parenthesis, keeping in mind the stack data structure. I used two lists instead to check if a bracket matches another
hey im not sure if i understand correctly, but wouldn't the stack.pop () function only remove the closed parenthesis, but leave the open parenthesis in the stack?
The rules are clear. An input string is valid if : 1) Open bracketes must be closed by the same type of brackets. 2) Open brackets must be closed in the correct order. A string }() should be valid. Because 1. and 2. are valid. The rules don't say anything about closed brackets needs to have an open bracket.
try: for b in x: if b in opening_brackets: stack.append(b) elif b in opening_brackets.values(): if len(stack) == 0 or opening_brackets[stack.pop()] != b: return False
Cant we use an if else condition instead of using a hash-map although it doesnt really matter in this case because the space complexity for both these cases will still be O (1) because the values we store in the hash-map dont increase with the size of the input.
This is weird. When I copied the code of Neetcode and put it in Leetcode, it works. Then, when I debug it, it returns the wrong thing which is False. It is supposed to be True. I submit it and it works. The leetcode debugger might be glitchy or something.
Great video! The subtitles are in Vietnamese, can they be changed to English? There are some parts that I don't understand, although I still have to translate into traditional Chinese. If possible, I would be very grateful.
Hello great video but can someone explain why at the line if stack[-1] == closeToOpen we access the last element? Shouldn't the last element be a closing paranthese? Wouldn't that like trying to find an opening paranthese at the end of stack?
I was confused with the same doubt for alot of time but then finally understood. What you need to remember is that according to the logic of the code, only opening parenthesis' will be added to the stack, not the closing ones. Now with that in mind, consider the string to be " ( ) " The first character is ( which is an opening parenthesis which will be appended to the stack, now the next character in the string is ) which is closing parenthesis and according to the code we will now be checking the last element of the stack (we are not appending this character to the stack, just checking it). The last element of the stack matches with the value of the closing parenthesis in the hashmap. Apply the same logic to the other test cases and you will completely understand. Write it down on a paper don't try to do it all in your head.
This is 3 months late sorry. A stack is Last in First out (LIFO). Think of putting(pushing/adding) the opening brackets into a thin glass jar and with it being so thin, you can only take out the last item you placed into it. I'm sure you've already worked this out but just in the off chance.
@@DeepakChauhan-wu7ei if test with s="[{()}]" the first 3 loops of the function will make stack=["[", "{", "("] and stack[-1]="(", but from what I understand stack don't match any keys in the hashmap and the if stack and stack[-1] == closeToopen[c] statement can't be execute?
@@suphawatwong9438 It will keep on adding it top of the stack until it find closing parentheses like ')' in your case, now ')' =='(' it will remove it from stack and repeat the process until it's empty
Noob question here: Even though it's not necessary for the solution, would it make sense at the beginning to count the number of each type of opening brackets in the string and compare to the number of each type of closing brackets in the string? Therefore if for example a string had 3 '(' in it but only 2 ')' then we would automatically know the output would be false. Would this be useful for saving time at all?
no bc then u still wont know if theyre matching up to each other or not, it could be like : (] [(, theres 2 of each paranthases and bracket but still its incorrect
While the solution here is easily understandable, a bigger challenge is how to get your train of thought to go in the right direction to begin with. I believe most people who have started off by writing the hash table in the form of {"(":")", "{":"}", "[":"]"}, which is intuitive and natural. From here on, the train of thought would have gone in a totally different direction.
I agree. I think the intuitive thought is to write the hashmap like that but I can see other ppl eventually figuring out that its easier to check the values by setting it the other way
I managed to solve this by myself, using same approach as shown in the video. -> My first thought wasn't even to create a hashmap, I only started with just a set of closed parenthesis. -> I then realized that whenever I see a closed parenthesis (matching from set), I will need to pop from stack. -> Then I realized, it would be easier to have a hashmap like shown in the video. so it wasn't actually that I thought of using a hashmap in the beginning, but rather at the end.
@mrruixiangz You can still do it that way though, and the internal logic within the loop can be pretty much the exact same, just reversed. You just instead are checking if c is an open parentheses, then add it to the stack, and if not (c is a closed parentheses) then check if c equals the hashmap value for the last item in the stack (if stack not empty).
When I was watching this video, I found that the automatically generated subtitles are in Vietnamese, can it be changed to English? Thank you for uploading these videos
wondering why we are starting with the inverse order for the hash map meaning ")":"(" instead of "(":")" seems logical to keep the order in the way it will be presented as True
If you've gone through the whole string, and there is still an opening parenthesis left in the stack, it means that there was no matching closing parenthesis for that one. That makes the string invalid.
leet code is showing answer is wrong but if I change last line of code to "return True if stack else false " than it work properly .. btw nice explanation
Think of it as using if/else logic. If not stack (if the stack is empty) it means every pair had its match, so we return True. If there's still something in the stack, it means there are still brackets left to close, so we return False
Which is why watching videos is not that helpful. You need to build your problem solving skills so that you can do it even if you've forgotten the video. I just repeated this problem 5 months after I first did it. It took me 8 minutes instead of 20, and the code was more readable. This isn't to put anyone down. Just to say that people shouldn't become dependent on solution videos, and they should ensure they're actually improving.
The best way to visualize is to loop thought it which reads from the left, as long as you see open one then you add to the stack, the trick is once you see close one then the one before it must be open one of its type which was last added to the stack. The first three loops will be open. Once you reach fourth ) then you check the stack of last one added which was ( so it matches.
is anything wrong with doing it like this? class Solution: def isValid(self, s: str) -> bool: hashMap = { ")" : "(", "}" : "{", "]" : "[" } stack = []; for c in s: if c in hashMap: if not stack or stack.pop() != hashMap[c]: return False else: stack.append(c)
you're explanations are like someone else showed you how to do it and you memorized it, you go so deep on the most obvious things but completely ignore detail in the more complex aspects like skipping over the hash map, you literally said 'you can probably guess what im doing here' no dude this is literally the most complex aspect of the entire program.
I think it's "obvious" to an audience that's actively grinding out leetcode problems. If you haven't finished your first year of CS where the proof was drilled into your head or ran into the concept of a hashmap or hashing in general, then yes it seems complex. As for everyone else, searching by index is pretty common data structure and that it has O(1) for adding, deleting, and searching. It comes from analyzing the best case, avg case, and worst case (big omega, big theta, big O) of other algorithms and finding a balance of sacrificing space complexity for time complexity. There's a handful of other proofs that are taken for granted due to the audience usually coming from a CS / University background, like why the average height of a BST is log(n) or
Im pretty worried about myself. I feel silly bcz i just tried for 9 hours straight to solve this and it never worked, i just dont feel enough for solving this kind of problems, like, how tf i would come up with this solution?
🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤
Better explanation than all the "Google employees" creating tutorials
Funny now, after knowing he is an Google employee :)
@@dima636363 haha
now he works in Google
Google employees are better than google employees
Because, he isn't only a Google employee, he is a teacher as well.
this channel has been a blessing, please keep updating this channel :')
Thanks. Also you can add a check on top if the size of the string is odd. And if its is, return false before checking anything else. Because that's just O(1) check assuring that anything can be closed at all (you can't close each bracket if the sum of chars is not even).
That's smart
cool
@@adarshsasidharan254 This is definitely a smart idea although remember some variations of this problem asked contain random chars other than brackets. This check would obv give a wrong result then.
@@AD-np2sh Then you can keep a count each and if they are != return false
A base case can be added at the beginning that checks if the string length is odd and if so return false.
This can optimize the time to O(1) if the string is odd (since there will be one bracket without a pair).
Man I got asked this question today and totally bombed it. I had a recursive implementation that kind of worked but missed a bunch of cases. Well back to learning it is. Your channel and experience is a truly godsent.
which company were you interviewing for??
which
luv that u explain the detail to all levels, like why a stack is helpful here & you lead listeners to suspect such a thing themselves ... super kind way, directly helpful 2 getting ppl into the mindset of solving these problems. mad thx
I was in the ball park with the hashmap, the stack, and the general idea, but handling the edge cases stumped me. Streamlined your code on my end just to make sure I understand it, thanks!
Thanks!
Your channel helps me get an offer! Thank you so much!!! Keep on the great work :)
That's awesome! Congrats 🎉
Very straightforward explanation, thank you!
You’re actually good, I really hope I don’t fumble this opportunity and I get what I want with this
just changing the last return to: return stack == [] makes the runtime MUCH BETTER
Definitely. "return not stack" also works and may be faster because it avoids an explicit comparison and directly evaluates the truthiness.
I only use c++ but I like looking at your explanations since you make it so simple to understand.
Thank you for sharing with us all your knowledge, its a big thing to do
Hey, just want to let you know that I absulutely LOVE neetcode and all your videos. I'm a huge fan! Also, the code that you have on neetcode for this problem is a little different. I like the one from this video a lot better!
Super helpful! Had trouble doing this on my own, learned a lot by doing your approach.
i also used the stack data structure but use the if and else conditions therefor i came here to see more optimal and easy way and i got what i expect from your channel, thank you so much.
Hey thanks for the video. I fought with this problem quite a lot. Had not heard about stacks before. I did not find this problem an easy one to be honest. Thanks for the explanation!
This problem is extremely difficult for me. Thank you for your tutorial once again.
Love your clear explanation with simple code. You're the best. Thanks!
Your explanation was perfect, yet I'm afraid I didn't understand that I wasn't able to solve this problem because I didn't know how to work with stack data structures. Good job my friend!
Hi Sir, thank you for the amazing roadmap! I have a suggestion: could you clone the same roadmaop and avoid mentioning the category of each problem? Knowing the category often gives away the approach, which takes away the challenge. For example, when I saw that this problem labeled "stack" I solved it quickly but missed the chance to think critically. Removing the categories could make the learning process even more effective. Thanks again for all your efforts! 🌹
How the hell is this considered an easy problem?
I definitely need more work -.-
Agreed, the trick is actually hard to pick so anyone who can solve most likely knows the trick or it would be hard. The code is easy though but not the strategy.
You did it way smarter than what I tried to. I made a hash table but I did one where the opening parentheses are they keys not the vales, the other way way is much simplier.
How is it any different?
def isValid(s: str) -> bool:
char_map = {"(": ")", "[": "]", "{": "}"}
stack = deque()
for c in s:
if c in list(char_map.keys()):
stack.append(c)
else:
if not stack or char_map[stack.pop()] != c:
return False
return not stack
The fact that this is easy is a little discouraging considering I fumbled around with it for several hours since I didn't know what a stack is. Glad to be able to learn this now though!
were all in this together brother
you aren't alone man lol. My advice is to not spend hours though, just go to the solution if it takes an hour
You can slightly simplify this using only stack.pop() instead of stack[-1] and then stack.pop() as stack.pop() also returns the value you wanted to check, if its False we're exiting the function, if its True then we both did the verification of the value AND we performed the stack.pop() that we will need e.g.
for char in s:
if char in close_to_open:
if stack.pop() != close_to_open[char]:
return False
else:
stack.append(char)
I guess I'm getting a hang of DSA 😅. I was able to solve this myself. Great content as always.
8:30 I think we dont need to necessarily check if the first char is closing parentheses then is not valid, we can 'return not stack' and get the case covered
My first attempt was to use a deque as a stack but using a list works just fine. Thanks
Thank you, Neetcode! Have a happy holiday season!
Awesome content.
Thank you so much 🙏
"return True if not stack else False" is a bit of a strange one IMO. You can just write "return not stack"
True, but it helps when he writes it out in dumb speech like that. In an interview it would probably also help to know that you can write it out both ways.
also, this one ## return len(p_stack) == 0 ## work fine
I actually prefer the guard clause, if stack -> return False, then a bare return True at the end
@@pauljones9150 I interviewed many candidates at Google; if someone wrote that on the whiteboard it'd be a red flag. No one should be writing production code this way and such unnecessary code would be flagged at review time.
After doing a few of these challenges, coding feels like tricks to manipulate stuff to get what you want. So different from other subjects
Thank you! I was staring at the solution code thinking I would never understand 😂
i started from working around Dijkstra's Two Stack algorithm which uses similar logic and managed to do it without using hash map, but it required from me handling popping from an empty stack and also resulted in longer and dirtier (although simple to understand) code.
this one took me a good 30 minutes. all I knew going into it was that it utilized the stack data structure. I was able to come up with the logic for it by thinking about how I would solve it just in my head if someone presented me with a sequence of parenthesis, keeping in mind the stack data structure. I used two lists instead to check if a bracket matches another
@@mightyoranje did u know what a a stack was before hand? I think that’s the main thing
the channel gives me so much hope hehe
lots of edge cases on this easy to watch for
Best explanation of this problem so far
does it make sense to check: if len(s) % 2 != 0: return False ?
not for this kind of solution, an odd length string would return false anyways
I think it would make the code faster btw
hey im not sure if i understand correctly, but wouldn't the stack.pop () function only remove the closed parenthesis, but leave the open parenthesis in the stack?
The closing parentheses are never added to the stack. So stack.pop() will only remove the opening parentheses that matches the closing one.
Great Explanation 👌👌
The rules are clear. An input string is valid if : 1) Open bracketes must be closed by the same type of brackets. 2) Open brackets must be closed in the correct order.
A string }() should be valid. Because 1. and 2. are valid. The rules don't say anything about closed brackets needs to have an open bracket.
class Solution:
def ispar(self,x):
opening_brackets = {'{': '}', '[': ']', '(': ')'}
stack = []
try:
for b in x:
if b in opening_brackets:
stack.append(b)
elif b in opening_brackets.values():
if len(stack) == 0 or opening_brackets[stack.pop()] != b:
return False
if len(stack) > 0:
return False
except:
return False
return True
Cant we use an if else condition instead of using a hash-map although it doesnt really matter in this case because the space complexity for both these cases will still be O (1) because the values we store in the hash-map dont increase with the size of the input.
Wow!. A very cut clear explanation. Thanks
This is weird. When I copied the code of Neetcode and put it in Leetcode, it works. Then, when I debug it, it returns the wrong thing which is False. It is supposed to be True. I submit it and it works. The leetcode debugger might be glitchy or something.
Great video! The subtitles are in Vietnamese, can they be changed to English? There are some parts that I don't understand, although I still have to translate into traditional Chinese. If possible, I would be very grateful.
Hello great video but can someone explain why at the line if stack[-1] == closeToOpen we access the last element? Shouldn't the last element be a closing paranthese? Wouldn't that like trying to find an opening paranthese at the end of stack?
I was confused with the same doubt for alot of time but then finally understood.
What you need to remember is that according to the logic of the code, only opening parenthesis' will be added to the stack, not the closing ones.
Now with that in mind, consider the string to be " ( ) "
The first character is ( which is an opening parenthesis which will be appended to the stack, now the next character in the string is ) which is closing parenthesis and according to the code we will now be checking the last element of the stack (we are not appending this character to the stack, just checking it). The last element of the stack matches with the value of the closing parenthesis in the hashmap.
Apply the same logic to the other test cases and you will completely understand. Write it down on a paper don't try to do it all in your head.
in the closeToOpen[c] line, does 'c' mean complement? is that the syntax of writing the complement of a hashmap ?
yeah you're getting the value for key "c" in the closeToOpen dictionary, it's just the python syntax
thats just the iterator in the 7th line "if c in closeToOpen:"
Sorry. I am pretty new to programming. What does term stack mean in here?
This is 3 months late sorry.
A stack is Last in First out (LIFO).
Think of putting(pushing/adding) the opening brackets into a thin glass jar and with it being so thin, you can only take out the last item you placed into it.
I'm sure you've already worked this out but just in the off chance.
I can't understand why stack can equal to closeToopen[i]. I mean that I know it prevent the empty array but I'm confuse.
It is just checking if stack is matching the keys in the hashmap. It can be equal only if it's already in the hashmap
@@DeepakChauhan-wu7ei if test with s="[{()}]" the first 3 loops of the function will make stack=["[", "{", "("] and stack[-1]="(", but from what I understand stack don't match any keys in the hashmap and the if stack and stack[-1] == closeToopen[c] statement can't be execute?
@@suphawatwong9438 It will keep on adding it top of the stack until it find closing parentheses like ')' in your case, now ')' =='(' it will remove it from stack and repeat the process until it's empty
Noob question here: Even though it's not necessary for the solution, would it make sense at the beginning to count the number of each type of opening brackets in the string and compare to the number of each type of closing brackets in the string? Therefore if for example a string had 3 '(' in it but only 2 ')' then we would automatically know the output would be false. Would this be useful for saving time at all?
no bc then u still wont know if theyre matching up to each other or not, it could be like : (] [(, theres 2 of each paranthases and bracket but still its incorrect
nice and clear explantion
Thank you, please keep up the good work.
While the solution here is easily understandable, a bigger challenge is how to get your train of thought to go in the right direction to begin with. I believe most people who have started off by writing the hash table in the form of {"(":")", "{":"}", "[":"]"}, which is intuitive and natural. From here on, the train of thought would have gone in a totally different direction.
I agree. I think the intuitive thought is to write the hashmap like that but I can see other ppl eventually figuring out that its easier to check the values by setting it the other way
I managed to solve this by myself, using same approach as shown in the video.
-> My first thought wasn't even to create a hashmap, I only started with just a set of closed parenthesis.
-> I then realized that whenever I see a closed parenthesis (matching from set), I will need to pop from stack.
-> Then I realized, it would be easier to have a hashmap like shown in the video.
so it wasn't actually that I thought of using a hashmap in the beginning, but rather at the end.
@mrruixiangz You can still do it that way though, and the internal logic within the loop can be pretty much the exact same, just reversed. You just instead are checking if c is an open parentheses, then add it to the stack, and if not (c is a closed parentheses) then check if c equals the hashmap value for the last item in the stack (if stack not empty).
Why is the closeToOpen dictionary not considered another object, making the space complexity O(2n) ?
because it’s length is not a factor of the string length it is a constant length of 3
no matter how big the input size of the array is, the hashmap stays at a constant O(3) which is just O(1) and O(n) + O(1) is just O(n)
why do you just pop last index
can it be done recursivly?
thanks for good explanation!
It’s super clear!
I kept doing s.replace(‘()’, ‘’) til empty, but your way looks much faster.
Excellent!! Thank you so much
awesome explanation
Dijkstras two stack algorithm helped me come to this conclusion
return not stack
genius 👏👏
You can use Switch Concept
When I was watching this video, I found that the automatically generated subtitles are in Vietnamese, can it be changed to English? Thank you for uploading these videos
wondering why we are starting with the inverse order for the hash map meaning ")":"(" instead of "(":")" seems logical to keep the order in the way it will be presented as True
test failed for input = " ] "
I added a condition to the if statement on line 8
if c in closeToOpen and len(stack) != 0:
i think u didnt put return statement in 1st else condition
Thanks so much for the helpful video. Why do you need to write 'if not stack' in the last line?
If you've gone through the whole string, and there is still an opening parenthesis left in the stack, it means that there was no matching closing parenthesis for that one. That makes the string invalid.
How come map here does not factor into space- time complexity?
probably he just discarded as it will be 2n, and at the end n
Good. ternary at the bottom is unnecessary. not stack is already a bool expression
But he didn’t add anything to the stack? It’s still empty, so how does this work?
Thank you so much
Super helpful!!!!
was asked question this today!
how did it go?
Which company??
@@usa5450 SAP
@@AndrewLor ok 👍🏻
@@AndrewLor you got selected??
leet code is showing answer is wrong but if I change last line of code to "return True if stack else false " than it work properly ..
btw nice explanation
New to python. Can you explaine more about return Ture if not stact else false?
Think of it as using if/else logic. If not stack (if the stack is empty) it means every pair had its match, so we return True. If there's still something in the stack, it means there are still brackets left to close, so we return False
I can't even solve an easy problem... I feel really stupid
+1
oh right we can actually just use a list in reverse order.
saves me from messing with deque data structure
I would just return "not stack". Should be enough.
Congratulations to me who screwed the interview round over this problem.
What's worst is I'd already watched this video 1-2 months back!
Shame.
it's okay, you'll get it next time !!
may I ask how you screwed up, did you forget how to do some part of it?
Which is why watching videos is not that helpful. You need to build your problem solving skills so that you can do it even if you've forgotten the video.
I just repeated this problem 5 months after I first did it. It took me 8 minutes instead of 20, and the code was more readable.
This isn't to put anyone down. Just to say that people shouldn't become dependent on solution videos, and they should ensure they're actually improving.
doesnt this return false if the test case is ( [ ) ]? Because it returns false since ( doesnt equal [ in the third iteration of s
it does, which is correct; ( [ ) ] is not valid way of using parentheses. ("Open brackets must be closed in the correct order")
@@sarahf1871 Yeah I noticed that shortly after as well, thanks for letting me know
I am still not able to process how is this a easy difficulty problem in leet code.
How will stack[-1] always match with the correct ?
In case it's something like [{()}]
The best way to visualize is to loop thought it which reads from the left, as long as you see open one then you add to the stack, the trick is once you see close one then the one before it must be open one of its type which was last added to the stack. The first three loops will be open. Once you reach fourth ) then you check the stack of last one added which was ( so it matches.
Testing this with the debug feature on VSCode does help a lot with wrapping your head around the functionality of this.
@@MrRenaissance17 Do you have any tutorial on how to do this?
the first closed brace you encounter must match the last open brace i.e stack[-1]
you're awesome!
Can we interchange not stack for True?
You are really cool!
Just bombed this question for a job 😢
is anything wrong with doing it like this?
class Solution:
def isValid(self, s: str) -> bool:
hashMap = {
")" : "(",
"}" : "{",
"]" : "["
}
stack = [];
for c in s:
if c in hashMap:
if not stack or stack.pop() != hashMap[c]:
return False
else:
stack.append(c)
return True if not stack else False
Please use underscore, respect pep.
U a God
you're explanations are like someone else showed you how to do it and you memorized it, you go so deep on the most obvious things but completely ignore detail in the more complex aspects like skipping over the hash map, you literally said 'you can probably guess what im doing here' no dude this is literally the most complex aspect of the entire program.
perfect example 8:30-8:50 help us out brother
I think it's "obvious" to an audience that's actively grinding out leetcode problems.
If you haven't finished your first year of CS where the proof was drilled into your head or ran into the concept of a hashmap or hashing in general, then yes it seems complex.
As for everyone else, searching by index is pretty common data structure and that it has O(1) for adding, deleting, and searching. It comes from analyzing the best case, avg case, and worst case (big omega, big theta, big O) of other algorithms and finding a balance of sacrificing space complexity for time complexity.
There's a handful of other proofs that are taken for granted due to the audience usually coming from a CS / University background, like why the average height of a BST is log(n) or
I feel kinda bad tho...This question is categorized as "easy" but I still had to go to NeetCode...
don’t worry about it. Just keep going. Took me over 80 problems To consistently get easy problems done
you are saver _/\_! Hence, subscribed and liked!
thank you:)
Im pretty worried about myself. I feel silly bcz i just tried for 9 hours straight to solve this and it never worked, i just dont feel enough for solving this kind of problems, like, how tf i would come up with this solution?
same bro, same. how do you feel about it now (4 months later)???
thanks :)