20. Valid Parentheses
You get a string s built entirely from the six bracket characters (, ), [, ], {, }. Return true if the string is well-formed, otherwise false.
Well-formed means every opener has a matching closer of the same kind, closers arrive in the reverse order their openers appeared (proper nesting, never ([)]), and no bracket is left unmatched.
So ([]{}) is good; (], ([)], and (( are not.
Example 1:
Input: s = "([]{})"
Output: true
Explanation: The square and curly pairs close inside the round pair, and every opener finds its matching closer in the right order.
Example 2:
Input: s = "([)]"
Output: false
Explanation: The round pair is still open when ] arrives, so the closers come in the wrong order — the pairs interleave instead of nesting.
Constraints:
- 1 ≤ s.length ≤ 10⁴
- s consists only of the characters ( ) [ ] { }
Hints:
The most recently opened bracket must be the first one to close. Which data structure hands you back the most recent thing you stored?
Push openers onto a stack. On a closer, the stack top must be the matching opener — pop it; any mismatch or an empty stack means invalid.
Don't forget the ending: a valid string leaves the stack empty. Leftover openers like "((" fail that final check. An odd-length string can never be valid.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "([]{})"
Expected output: true