You could also use a map for parens which I feel is more intuitive. Here's a solution I found easier to understand. /** * @param {string} s * @return {boolean} */ var isValid = function (s) { //handle the edge case //create a map holding the opening brackets macthed to the closing bracket //create a stack to hold the opening bracket //loop through s and check if the bracket in the stack matches the current bracket //if not push item to the stack //if stack is empty return true else false if (s.length % 2 != 0) return false; const map = { "(": ")", "[": "]", "{": "}" } const stack = []; stack.push(s[0]); for (let i = 1; i < s.length; i++) { let stackEl = stack[stack.length - 1]; if (map[stackEl] == s[i]) { stack.pop(); } else { stack.push(s[i]); } } return stack.length == 0; };
@udaykulkarni5639
Жыл бұрын
Love it! No bs. straight to the point. short and crisp! Thanks man.
@Michael-kp4bd
2 жыл бұрын
Subtle but important: putting spaces or some character between the matching pairs of parens to compare to. If you made the string ‘()[]{}’ instead of ‘() [] {}’ then you could accidentally (incorrectly) pop pairs like ‘)[ ‘ because the string INCLUDES that substring. This problem also seems to rely on an insight that any valid string inherently will have adjacent open/close parens. If parens are nested, they’ll be a palindrome and the pops out of the stack will only start once the middle is reached, and then it will cascade, popping matching pairs until there are none left. And - Any non nested open/close parens must be adjacent. That’s why you can check for open and close pairs corresponding to: open = stack[stack.length-2] and close = stack[stack.length-1] Without that insight, it’s unclear why testing open and close parens next to each other in the stack is sufficient in all cases.
@Michael-jq1hl
Жыл бұрын
Wait, so the problem never has two open parens in a row? Now it makes sense!
@andrewthomas9884
Жыл бұрын
@@Michael-jq1hl yeh.. I'm hoping someone can confirm whether you and I are misunderstanding how the code works, or the leetcode check for example 5 (towards the beginning of the video) isn't tested very well.
@rafaelmauricio2067
Жыл бұрын
This makes no sense to me whatsoever. It's still unclear to me why this solution works
@Michael-kp4bd
Жыл бұрын
@@Michael-jq1hl no, any sufficiently large case will certainly have 2 open parens in a row. It’s even in one of the examples on the side, e.g “{()}” Here’s a complicated example { ( ) ( [ ] ) } This covers a lot of cases: teo open parens to start, two expressions inside one large expression, and one of the two expressions has a nested expression (like example 5) Weee! Ok so this algorithm would go from the beginning to end by index, in the while loop, right? And it always checks for proper open/close pairs before it adds the next index to the stack, AND if VALID, it pops the those two out of the stack. (The check specifically happens on the current “Top” 2 of the stack (because it checks the indexes s.length-2 and s.length-1… aka the second-to-last and the last element in the stack so far!)
@Michael-kp4bd
Жыл бұрын
@@andrewthomas9884 Please see my comment above, with my more complicated example: { ( ) ( [ ] ) } And notice that this contains an element similar to example 5, notably elements 4-7, which look like ( [ ] ). Anyway, let’s get going! We’ll through each pass of my example, { ( ) ( [] ) } You can tell it’s valid, right? So let’s try the first pass. First, { gets added to the stack as s[0] . Nothing to compare it to, so nothing gets popped out of the stack. 2nd pass: Stack is now { ( These don’t match. s.length-1 is “(“ and s.length-2 is “{“. Again, nothing happens. Pass 3: stack is now { (). Boom! A condition is met! s.[length-2] is “(“ and s.[length-1] is “)” . This, aka “()” is contained in the parens string “ () [] {} ” !! Yay, so now the algorithm doesn’t just “check” that the last 2 are valid, it POPs them out of the stack. So the stack { ( ) Becomes { After the third pass! 4th pass: { ( 5th pass: { ( [ 6th pass adds a closing “]” to the top of the stack right after the opening “[”. Stack now looks like { ( [] But again, boom. Condition met. Pops “[] of the stack, so now it looks like { ( Again. Moving on to the 7th pass, we’re adding to the stack of pass 6 a “)”. Would look like { ( ) But boom, another match. Pop the “( )” and you’re left with { Again Pass 8: Stack is currently just { This pass adds the final brace in the example string. It’s “}” So we immediately have { } This is a match. It’s also the elements from the very first and very last parens. It’s a match. According to the algorithm, those 2 get popped off the stack. Stack is now empty. The function returns. See how due to valid parens, it eventually all cascades down to nothing? That’s why this works. (And If it were invalid, you’d be left with at least something dangling in the string and no more valid operations. Only thing to maybe improve is a return false after the while loop, but apparently it works without it 🤷♂️
@bidaarle
13 күн бұрын
This is a dope solution. How do you even think of that
@JasleenKaur-cl2ud
3 жыл бұрын
Great!
@reet5407
2 жыл бұрын
Thank you so much
@tomtran1458
2 жыл бұрын
Thank you 🙌🙏🏼
@SouravCheck
4 ай бұрын
hello, /** * @param {string} s * @return {boolean} */ var isValid = function(s) { let input=s.split(""); let count=0; for(let i=0;i
Пікірлер: 17