You are given a string s that has only the brackets '(', ')', '{', '}', '[' and ']'. Return true if the string is valid, and false if it is not.
A string is valid when all three rules below hold:
- Every opening bracket is closed by a bracket of the same kind.
- Brackets are closed in the right order: the last one opened is the first one closed.
- Every closing bracket has an opening bracket of its kind before it.
Examples
Example 1:
Input: s = "{[()]}"
Output: true
Explanation: Every bracket is closed in the right order.
Example 2:
Input: s = "[{]}"
Output: false
Explanation: The square bracket ] comes while the curly bracket { is still open, so the order is wrong.
Example 3:
Input: s = "(("
Output: false
Explanation: Two brackets are opened and never closed.