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
trueThe string already contains a matching pair of parentheses.
Example 2
Input
s = "(*)"Output
trueThe
* can be treated as an empty string, leaving a valid pair of parentheses.Constraints
- 1 <= s.length <= 100
- s[i] is '(' , ')' or '*'.