Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if: 1) Open brackets are closed by the same type of brackets. 2) Open brackets are closed in the correct order. 3) Every close bracket has a corresponding open bracket.
Examples
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]"
Output: false
Example 4:
Input: s = "([)]"
Output: false
Example 5:
Input: s = "{[]}"
Output: true
Constraints
1 <= s.length <= 10^4
s consists of parentheses only '()[]{}'.
Prerequisites
Stacks — last in, first out, and why that is the right shape for nesting.
How to think about it
1. Stack of Expected Closers Optimal
Intuition
Nesting is last-in-first-out, which is the definition of a stack. Every opening bracket promises a matching closer, and the most recent promise must be kept first — so push what you expect to see, and check each closer against the top.
Algorithm
1. For an opening bracket, push its matching closer. 2. For a closing bracket, it must equal the top of the stack — otherwise the string is invalid. 3. A closer arriving on an empty stack is invalid too. 4. Valid exactly when the stack ends empty; leftovers are unclosed openers.
Time & Space
Time O(n). Space O(n) in the worst case, when every character is an opener.