cheetcode

129. Valid Parenthesis StringMedium

Validate a parenthesis string where stars can act as open, close, or empty.

You are given a string s containing only '(', ')' and '*'.

Return true if the string can be valid after treating each '*' as '(', ')' or an empty string.

Examples

Input: s = "()"
Output: true

Input: s = "(*)"
Output: true

Input: s = "(*))"
Output: true

Constraints

  • 1 <= s.length <= 100
  • s contains only '(', ')' and '*'.