Valid Parenthesis String
Part of Practice: Clever Commitments
You are given a string s containing only three characters: (, ), and *. Each * is a wildcard you may treat as an open parenthesis, a close parenthesis, or an empty string. Return true if some choice of interpretations for all the wildcards makes s a valid parenthesis string — every ( closed by a later ), every ) opened by an earlier (.
Constraints that matter: up to 100 characters, but the intended solution is linear — trying all 3^k wildcard interpretations blows up fast, and the trick is tracking a range of possibilities instead of individual ones.
Examples
- Input:
- s = "()"
- Output:
- true
- Input:
- s = "(*))"
- Output:
- true
Treat the * as an open parenthesis: "(())" is valid.
- Input:
- s = "*)("
- Output:
- false
The final "(" can never be closed — nothing follows it. No wildcard interpretation fixes an unmatched open at the end.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.