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
  • Justification: The asterisk can be treated as an open parenthesis, making the string "(())."

• Example 2:

  • **Input: s = "((*()**"
  • Expected Output: true
  • **Justification: The first and second asterisks can be treated as close parenthesis, and the third asterisk can be treated as an empty string, resulting in a balanced set of parentheses "(()())."

• Example 3:

  • Input: s = "())*"
  • Expected Output: false
  • Justification: There's no way to interpret the asterisk that would balance the extra close parenthesis at the start.

Try it yourself

Try solving this question here: