Problem of the day
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.
The first line of input contains an integer 'T' representing the number of test cases or queries to run. Then the test case follows.
The only line of each test case contains a string 'S'.
Output Format:
For each test case print 'Yes' if the string 'S' is a valid string otherwise print 'No' otherwise.
The output of each test case will be printed in a separate line.
Note:
You are not required to print the expected output; it has already been taken care of. Just implement the function.
1 <= T <= 100
1 <= N <= 5000
Where 'N' is the length of the string 'S'.
Time Limit: 1 sec
3
*())
(*)
())*
Yes
Yes
No
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.
1
((***
Yes
Try each of the three possibilities for every asterisk in the string.
We can try each of the three possibilities for every asterisk in the string with the help of recursion.
We will use a temporary string which will keep track of our current possible string. In the end, we can linearly check each possible string. If any of the possible string is a valid string, we print ‘Yes’, otherwise ‘No’.
O(N * 3^N), where ‘N’ is the length of the string.
In the worst-case scenario, we can have all the characters in the string as asterisks. So, we will be trying 3^N possible strings and check all of them in linear time for validity. Hence the overall complexity will be O(N* 3^N)
O(N), where ‘N’ is the length of the string.
In the worst-case scenario, our temporary string can have a length of at most the length of the given string. Also, our recursion stack can grow at most the length of the string. Hence the overall time complexity is O(N).