Valid String
Last Updated: 30 Sep, 2020
Difficulty: Moderate
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.
Input Format:
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.
Constraints:
1 <= T <= 100
1 <= N <= 5000
Where 'N' is the length of the string 'S'.
Time Limit: 1 sec
Approach 1
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’.
Approach 2
The problem can be divided into smaller sub-problems and hence, we can use a dynamic programming approach which will be similar to the Matrix Chain Multiplication’s dynamic programming approach.
Consider a boolean 2d matrix ‘DP’, where ‘DP[i][j]’ is whether the interval ‘S[i]’, ‘S[i + 1]’, ..., ‘S[j]’ can be made valid or not.
Now, ‘DP[i][j]’ is true only if either of the following two conditions is true:
- ‘S[i]’ is '*', and the interval ‘S[i + 1]’, ‘S[i + 2]’, ..., ‘S[j]’ can be made valid.
- ‘S[i]’ can be made to be '(', and there is some ‘K’ in the interval [i+1, j] such that ‘S[K]’ can be made to be ')'.
- Plus the two intervals cut by ‘S[K]’ (i.e. ‘S[i+1: K]’ and ‘S[K+1: j+1]') can be made valid.
‘DP[0][N-1]’ will be our answer if the whole string is a valid string or not.
Approach 3
Let’s first focus on the problem when there are no asterisks. For this problem, we can just use a variable to count the unmatched ‘(‘. Clearly, we don't want the value of this variable to be less than 0 at any time and it should be 0 when the whole string has been matched.
Now, when the asterisk is introduced, this variable or number becomes a range, indicating the number of possible unmatched ‘(‘ found. One asterisk just expands this range by 1 and we can use the same principle to check if the above criteria is within the range.
Here, is the complete algorithm-
- Initialize ‘LEAST_OPEN’ to 0, which indicates the least number of unmatched ‘(‘ possible.
- Initialize ‘MAXIMUM_OPEN’ to 0, which indicates the maximum number of unmatched ‘(‘ possible.
- Loop for every character in ‘S’
- If a ‘(‘ is found, increment both ‘LEAST_OPEN’ and ‘MAXIMUM_OPEN' by 1.
- If a ‘)‘ is found, decrement both ‘LEAST_OPEN’ and ‘MAXIMUM_OPEN’ by 1.
- If a ‘*’ is found, we have two choices
- Use it as a ‘(‘, hence increment ‘MAXIMUM_OPEN’ by 1.
- Use it as a ‘)‘, hence decrement ‘LEAST_OPEN’ by 1.
- Using it as an empty string won’t affect the range.
- Set ‘LEAST_OPEN’ to maximum of 0 and ‘LEAST_OPEN’.
- If ‘MAXIMUM_OPEN’ is less than zero, Return false.
- Return true if the value of ‘LEAST_OPEN’ is 0, else false.
