Loading problem…
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 ')' or a single left parenthesis '(' or an empty string "".
Example 1
Input: s = ()
Output: true
Explanation: The '(' is closed by the ')', and there are no wildcards to worry about.
Example 2
Input: s = (*)
Output: true
Explanation: Treat '*' as an empty string, leaving "()", which is balanced.
Example 3
Input: s = (*))
Output: true
Explanation: Treat '*' as '(' to get "(())", which is balanced.
Track the range [lo, hi] of how many '(' could still be open. A '*' widens the range (it might be '(', ')' or empty); if hi ever goes negative there are too many ')', and if lo can reach 0 by the end the string is valid.
Run checks all cases above. Submit evaluates all test cases.