453. Valid Parenthesis String
You are given a string s built from three characters: '(', ')', and '*'. Every '*' is a wildcard — before the string is checked, you choose independently for each star whether it becomes a single '(', a single ')', or nothing at all.
Return true if at least one choice of star meanings turns s into a valid parenthesis string: every '(' is closed by a ')' somewhere after it, every ')' closes a '(' somewhere before it, and no prefix ever has more closers than openers. Return false if no assignment works.
Example 1:
Input: s = "()"
Output: true
Explanation: The string is already balanced; no stars need deciding.
Example 2:
Input: s = "(*))"
Output: true
Explanation: Turn the star into '(' to get "(())", which is valid.
Example 3:
Input: s = "(*("
Output: false
Explanation: The last '(' can never be closed — no star sits after it, so every assignment leaves it unmatched.
Constraints:
- 1 ≤ s.length ≤ 100
- s[i] is '(', ')' or '*'
Hints:
Each star has three possible meanings, so a decision tree with 3^k leaves exists. While scanning left to right, what single piece of state decides validity — and how do the three choices change it?
The count of unmatched '(' is no longer one number once stars appear: it is a whole range [lo, hi]. Update both ends per character ('(' adds 1 to both, ')' subtracts 1 from both, '*' widens the range by 1 each way), clamp lo at 0, and fail the instant hi drops below 0. The string is valid iff lo can land on 0 at the end.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "()"
Expected output: true