Problem Statement

Given a string s containing multiple occurrences of characters: '(', ')' and '*', return true if s is valid. Otherwise, return false.

A string is valid if it follows below rules:

• Any left parenthesis '(' must be closed by corresponding right parenthesis ')'.
• Any right parenthesis ')' must have a corresponding left parenthesis '('.
• '*' can be used as a single left parenthesis ')' or a single right parenthesis '(' or an empty string "".

Examples

• Example 1:
  • Input: s= "*())"
  • Expected Output: true