Valid Parenthesis String
The key idea
Each
'*' is a wildcard: '(', ')', or empty. Instead of trying every choice, track the RANGE of possible open-paren counts as [low, high]. low assumes every '*' so far closed; high assumes every '*' opened. The string is valid iff this range can reach exactly zero, never letting low go negative.Problem
Given a string s containing only three types of characters: '(', ')', and '*', return true if s is valid.
The string is valid if all of the following rules hold:
- 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 ')'.
- A '*' could be treated as a single right parenthesis ')', a single left parenthesis '(', or an empty string "".
Constraints
1 <= s.length <= 100s[i]is'(',')', or'*'.
Examples
Input: s = "()"
Output: true
Input: s = "(*)"
Output: true
Input: s = "(*))"
Output: true
Complexity
Time: O(n) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Greedy problems
- Assign CookiesEASY
- Best Time to Buy and Sell Stock IIMEDIUM
- Boats to Save PeopleMEDIUM
- Can Place FlowersEASY
- CandyHARD
- Dota2 SenateMEDIUM
- Gas StationMEDIUM
- Hand of StraightsMEDIUM
- Increasing Triplet SubsequenceMEDIUM
- Jump GameMEDIUM
- Jump Game IIMEDIUM
- Lemonade ChangeEASY