Valid Parenthesis String

The problem Given a string s containing only three types of characters: '(', ')', and '*', return true if s is valid. The following rules define a valid string: Any left parenthesis '(' must have a corresponding right parenthesis ')'. Any right parenthesis ')' must have a corresponding left parenthesis '('. A left parenthesis '(' must go before the corresponding right parenthesis ')'. '*' could be treated as a single right parenthesis ')', a single left parenthesis '(', or an empty string "". Example 1: ...