Valid Parenthesis String

Given a string s containing only (, ) and *, return whether it can be a valid parenthesis string. Each * may represent (, ), or the empty string. Every prefix…

Given a string s containing only (, ) and `*`, return whether it can be a valid parenthesis string. Each `*` may represent (, ), or the empty string. Every prefix must be interpretable without a negative open-parenthesis balance, and the final balance must be zero.

- 1 <= s.length <= 10000 - s contains only (, ), and `*`. - The teaching trace accepts 1..8 characters; coding retains the complete source bound.

Example 1: input s = "(*))"; output true. Treat `*` as ( to obtain (()).

Example 2: input s = "*(()"; output false. No interpretation can close all opens without making a prefix invalid.

Category: Greedy Algorithms. Topic: greedy. Difficulty: Medium. Patterns: greedy, dynamic-programming.