Each test file starts with an integer ‘t’ — the number of testcases.
In each of the next ‘t’ lines, you are given a string of ‘n’ characters [ either ‘(‘ or ’)’ or ‘*’ ].
Your task is to find the number of distinct balanced parentheses expressions you can make by replacing the ‘*’ with either ‘(‘ or ‘)’ or removing the ‘*’
Note : You have to replace each ‘*’ with one of ‘(‘ or ‘)’ or remove it. If removed, assume the string has reduced by 1 character.
Duplicate strings are not allowed. The final expressions to be counted have to be distinct
As the answer may be large, please output it modulo 1000000007 (10^9+7)
Output one integer per line corresponding to each testcase.
Constraints :
1 <= t <= 20
1 <= n <= 100
0 <= Number of ‘*’ in the input string <= min(n,10)
Sample Input:
2
(*(*)*)
((**)*
Sample Output
5
9
Explanation
The five possible valid solutions are for the first input are :
((()))
()(())
()()()
(())()
(())
The nine possible valid solutions are for the second input are :
(((())))
(()(()))
(()()())
(()())
((()))
()(())
()()()
()()
(())
This is a classic dp problem. I would like to give hints so that you discover the solution by yourself. Denote dp[i][j] as the number of ways to get 'j' more brackets of the type '(' more than ')'. Note that j can be negative so add some constant to balance it out. Now you need to calculate dp[n-1][0] . Try to figure out the relation between dp[i][j] and dp[i+1][j+1],dp[i+1][j],dp[i+1][j-1]. Also don't forget to take the module at every step. This should lead you to the answer :) EDIT: I did not see that the parenthesis expressions have to be distinct and I can't delete this comment now :(
looks like a complete search will work because max number of '*' is 10 (lets call the number of stars k)
for every * there are 3 possibilities, ), (, or removed (this is O(3^k))
for every combination check if its a valid paranthesis O(N) (convert ( to +1, and ) to -1, and check if the sum is 0 and there is no negative number in the prefix sum) (also can be done using segment tree in O(log(n))
so complexixity is O(t * 3^k * N)
max test = 20 * 59049 * 100 = 118098000 (i guess its enough to pass)