Greedy The best choice now
497. Valid Parenthesis String
You are given a string s made only of the characters (, ) and *. Each * can stand for (, for ),
or for nothing at all, and each * makes its own choice.
Return true if some choice for the stars makes s balanced, and false otherwise.
A string of brackets is balanced when every ( is closed by a ) somewhere after it, and every ) closes
a ( somewhere before it. Read from left to right, the closing brackets never outnumber the opening ones so
far, and at the end the two counts are equal. The empty string is balanced.
Example 1
Input: s = "(*)*)"
trueExplanation: Make the first * an opening bracket and the second one nothing. The string becomes (()), which is
balanced.
Example 2
Input: s = "*)("
falseExplanation: The * can open a bracket for the ), but nothing comes after the last ( to close it.
Example 3
Input: s = "*"
trueExplanation: The * stands for nothing, and the empty string is balanced.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ s.length ≤ 105sholds only the characters(,)and*.
Clarifying questions
What you would ask an interviewer before writing any code.