Valid Parenthesis String

Given a string s containing only three types of characters: '(',')' and '*', return 1 if s is valid else return 0.

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 '('.
• Left parenthesis '(' must go before the corresponding right parenthesis ')'.
• '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string "".

Input Format

First Parameter: String s

Output Format

Return the number.

Example 1

Input: s = "()"
Output: 1

Example 2

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

Example 2

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

Constraints

• 1 <= s.length <= 100
• s[i]is '(', ')' or '*'.
• Expected Time Complexity - O(n )
• Expected Space Complexity - O(n)