Valid Parentheses
EasyStack
A string s contains only the characters (, ), [, ], { and }.
It is valid when every opening bracket is closed by a bracket of the same kind, the brackets close in the right order, and no closing bracket comes without an opening one. Return true if s is valid.
Examples
Input: s = "{[()]}"
Output: trueEach pair closes inside the pair around it.
Input: s = "([)]" Output: false
The [ is still open when ) tries to close the (.
Constraints
1 ≤ s.length ≤ 10⁴
Stuck?
Hint 1
Push each opening bracket onto a stack.
Hint 2
A closing bracket must match the bracket on top of the stack. At the end, the stack must be empty.
The idea
The bracket that has to close next is always the one opened most recently that is still open. A stack keeps exactly that order: push each opening bracket, and each closing bracket must match the one on top.
Time O(n)Extra space O(n)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 5
opener maps each closing bracket to the opening bracket it needs. It also tells the loop which characters are closing brackets.
function isValid(s) { const opener = { ')': '(', ']': '[', '}': '{' }; const stack = []; for (const c of s) { if (c in opener) { if (stack.pop() !== opener[c]) return false; } else { stack.push(c); } } return stack.length === 0;}The trap
One counter checks that there are as many closing brackets as opening ones. Every valid string passes that test, so valid inputs come out right. But the counter never checks which kind of bracket closes, or in what order: brackets that cross, or a closing bracket that comes before its opener, still bring the count back to zero.
function isValid(s) { let open = 0; // counts, but ignores kind and order for (const c of s) open += '([{'.includes(c) ? 1 : -1; return open === 0;}