Valid Parenthesis String in Python

You get a string s made of three characters: (, ) and *.

Return True if s can be a balanced string of brackets. Return False if it can't.

Each * can stand for (, for ), or for nothing. Every * makes its own choice.

In a balanced string, every ( is closed by a ) that comes after it. Every ) closes a ( that comes before it.

Example 1:

Input: s = "(*()"
Output: True
Explanation: Read the * as a ).
The string becomes ()().

Example 2:

Input: s = "**))*"
Output: True
Explanation: Read the first two * as (.
Read the last * as nothing.
The string becomes (()).

Example 3:

Input: s = "*)("
Output: False
Explanation: The ( at the end has nothing after it.
No choice for the * can close it.

Constraints:

• 1 to 100,000 characters.
• Each character is (, ) or *.