Given a string s containing only three types of characters: '(', ')' and '*', return true if s is valid.
The '*' could be treated as '(', ')', or an empty string.
Example 1:
Input: s = "()" Output: true
Example 2:
Input: s = "(*)" Output: true
Example 3:
Input: s = "(*))" Output: true
Constraints:
1 <= s.length <= 100