Valid Parenthesis String

Medium · Greedy

You are given a string made only of the characters '(', ')' and '*'. Each '*' can be treated as either '(', ')', or an empty string. Determine whether it is possible to choose an interpretation for every '*' so that the resulting string becomes a valid parenthesis sequence, where every '(' has a matching later ')' and parentheses never close before they open. Return true if some choice makes it valid, false otherwise.

Examples

Input:  s = "()"
Output: true
Why:    The string is already balanced with no wildcards needed.

Input:  s = "(*)"
Output: true
Why:    Treating '*' as an empty string leaves "()", which is valid.

Input:  s = "(*))"
Output: true
Why:    Treating the '*' as '(' gives "(())", which is a valid sequence.

Constraints

1 <= s.length <= 100, s consists only of '(', ')' and '*'

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Valid Parenthesis String

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Valid Parenthesis String. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.