Valid Parenthesis String
Problem Statement
You are given a string s
which contains only three types of characters: '('
, ')'
and '*'
.
Return true
if s
is valid, otherwise return false
.
A string is valid if it follows all of the following rules:
- Every left parenthesis
'('
must have a corresponding right parenthesis')'
. - Every right parenthesis
')'
must have a corresponding left parenthesis'('
. - Left parenthesis
'('
must go before the corresponding right parenthesis')'
. - A
'*'
could be treated as a right parenthesis')'
character or a left parenthesis'('
character, or as an empty string""
.
Example 1:
# Example in Pythons = "((**)"# Returns: True
Explanation: One of the '*'
could be a ')'
and the other could be an empty string.
Example 2:
# Example in Pythons = "(((*)"# Returns: False
Explanation: The string is not valid because there is an extra '('
at the beginning, regardless of the extra '*'
.
Constraints:
1 <= s.length <= 100
Recommended Time and Space Complexity
Aim for O(n)
time and O(1)
space for optimal solutions.
Hint 1
Consider how ’*’ can act as ’(’ or ’)’ or an empty string.
Hint 2
Think about using stacks or dynamic programming to keep track of parenthesis counts.
Hint 3
A greedy approach might simplify the problem by tracking the possible range of open parentheses.
Solution
Recursion
def check_valid_string_recursive(s: str) -> bool: def dfs(i: int, open_count: int) -> bool: if open_count < 0: return False if i == len(s): return open_count == 0
if s[i] == '(': return dfs(i + 1, open_count + 1) elif s[i] == ')': return dfs(i + 1, open_count - 1) else: return (dfs(i + 1, open_count) or dfs(i + 1, open_count + 1) or dfs(i + 1, open_count - 1)) return dfs(0, 0)
Time complexity: O(3 ^ n)
Space complexity: O(n)