Determine whether a parenthesis string can be made valid when * may act as (, ), or an empty string.
Valid Parentheses String
gfgProblem
You are given a string s containing only the characters (, ) and *.
A string is valid if:
- every opening parenthesis has a matching closing parenthesis,
- parentheses are properly nested,
- and the empty string is considered valid.
Each * character can be treated as:
(, or), or- an empty string.
Return true if it is possible to replace every * so that the resulting string is valid. Otherwise, return false.
Notes
- You must consider all
*characters. - The replacement choices may differ for each
*. - The final string after replacements must be a well-formed parenthesis sequence.
Input Format
- A single string
s. sconsists only of'(',')', and'*'.
Output Format
- Return
trueifscan be transformed into a valid parenthesis string. - Otherwise, return
false.
Constraints
1 <= s.length <= 100s[i]is one of'(',')','*'
Example 1
Input
s = "(*)"
Output
true
Explanation
Treat * as an empty string, giving (), which is valid.
Example 2
Input
s = "(*))"
Output
true
Explanation
Treat * as (, giving (()), which is valid.
Show 1 more example
Example 3
Input
s = "((*)"
Output
true
Explanation
Treat * as ), giving ()(), which is valid.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.