Valid Parenthesis String

Medium · Greedy · about 20 minutes

Asked at Meta, Google, Amazon, Microsoft, Apple, Bloomberg.

Given a string s of '(', ')' and '*', return true if it can be a valid parentheses string, where each '*' may be treated as '(', ')' or an empty string.