# Valid String

Moderate
0/80
Average time to solve is 18m

## Problem statement

You have been given a string 'S' containing only three types of characters, i.e. '(', ')' and '*'.

A Valid String is defined as follows:

``````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.
5. An empty string is also valid.
``````

Your task is to find out whether the given string is a Valid String or not.

Detailed explanation ( Input/output format, Notes, Images )
Constraints:
``````1 <= T <= 100
1 <= N <= 5000

Where 'N' is the length of the string 'S'.

Time Limit: 1 sec
``````
##### Sample Input 1:
``````3
*())
(*)
())*
``````
##### Sample Output 1:
``````Yes
Yes
No
``````
##### Explanation of Sample 1:
``````In the first test case, we can replace '*' with '(' so that the string becomes "(())"

In the second test case, we can replace '*' with an empty string so that the string becomes "()"

In the third test case, there is no way to make the string a valid string.
``````
##### Sample Input 2:
``````1
((***
``````
##### Sample Output 2:
``````Yes
``````
Console