Valid parentheses string with wildcard.
Given a string containing only three types of characters: ‘(‘, ‘)’ and ‘*’. Write a function to check whether this string is valid.
We define the validity of a string by these rules:
1) Any left parenthesis ‘(‘ must have a corresponding right parenthesis ‘)’.
2) Any right parenthesis ‘)’ must have a corresponding left parenthesis ‘(‘.
3) Left parenthesis ‘(‘ must go before the corresponding right parenthesis ‘)’.
4) ‘*’ could be treated as a single right parenthesis ‘)’ or a single left parenthesis ‘(‘ or an empty string.
An empty string is also valid.
For Example –
Example 1:
Input: ” * ( ) ) “, Output: true
In the first example, To balance this string we need to treat star as opening bracket ( “(“).
Example 2:
Input: ” ( * ) “, Output: true
In this example, The start is treated as empty string.