Valid Parenthesis String
MediumGreedy
You are given a string s made of the characters (, ) and *. Each * is a wildcard that you may independently turn into (, into ), or into an empty string.
Return True if some choice for the wildcards makes s a valid parenthesis string, otherwise False. A string is valid when:
- every
(has a matching)somewhere after it, - every
)has a matching(somewhere before it, and - each parenthesis is matched at most once.
The empty string counts as valid.
Example 1
- Input:
- s = "(*()"
- Output:
- True
- Explanation
- Turn the
*into): the string becomes()(), which is valid.
Example 2
- Input:
- s = "((*)*("
- Output:
- False
- Explanation
- The final
(has nothing after it that could close it, so no choice of wildcards can make the string valid.
Example 3
- Input:
- s = "*)"
- Output:
- True
- Explanation
- Turning the
*into(gives().
Constraints
- 1 ≤
s.length≤ 100 s[i]is(,), or*