Valid Parenthesis String

Given a string s containing only three types of characters: '(', ')', and '*', return true if s is valid.

The following rules define a valid string:

• Any left parenthesis '(' must have a corresponding right parenthesis ')'.
• Any right parenthesis ')' must have a corresponding left parenthesis '('.
• Left parenthesis '(' must go before the corresponding right parenthesis ')'.
• '*' could be treated as a single right parenthesis ')', a single left parenthesis '(', or an empty string "".

---

Example 1

Input: s = "()"
Output: true
Explanation: A simple matched pair.

Example 2

Input: s = "(*)"
Output: true
Explanation: '*' is treated as ')' to match '(', or as '' leaving just ().

Example 3

Input: s = "(*))"
Output: true
Explanation: '*' is treated as '(' giving "(())", or as '' giving "()" with a trailing ')'. Either way it is valid.

---

Constraints

• 1 <= s.length <= 100
• s[i] is '(', ')', or '*'.