mediumStackPattern: Stack
Valid Parentheses String Solution
Problem Statement
Given a string `s` containing only the characters '(', ')', and '*', determine if the string is valid. A string is valid if and only if: 1. Any left parenthesis '(' must have a corresponding right parenthesis ')'. 2. Any right parenthesis ')' must have a corresponding left parenthesis '('. 3. Left parenthesis '(' must go before the corresponding right parenthesis ')'. 4. '*' can be treated as a single right parenthesis ')', a single left parenthesis '(', or an empty string "".
Examples
Example 1:
Input:()
Output:true
Explanation: The string is valid. The '(' has a matching ')' and they appear in the correct order.
Example 2:
Input:(*)
Output:true
Explanation: The '*' can be treated as an empty string, making the string '()', which is valid.
Example 3:
Input:(*))
Output:true
Explanation: The first '*' can be treated as '(', making the string '(())', which is valid. Alternatively, the first '*' can be an empty string, and the second ')' matches the '('. So the string becomes '()', which is valid.
Example 4:
Input:)(
Output:true
Explanation: The ')' appears before the '(', violating the order rule.
Constraints
- 1 <= s.length <= 100
- s[i] is either '(', ')', or '*'.
Time: O(n) Space: O(1)
A more efficient approach uses two variables to track the possible range of open parentheses. One variable tracks the minimum possible open parentheses count, and the other tracks the maximum. By iterating through the string and updating these counts based on the characters encountered, we can determine validity in linear time.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
def valid_parenthesis_string(s):
low = 0
high = 0
for char in s:
if char == '(':
low += 1
high += 1
elif char == ')':
low -= 1
high -= 1
else:
low -= 1 # '*' can be treated as ')'
high += 1 # '*' can be treated as '(' or empty
if high < 0:
return False # More closing brackets than possible opening brackets
low = max(low, 0) # Minimum balance cannot be negative
return low == 0