Problem Description
Robin bought a sequence consist of characters '('
, ')'
, '{'
, '}'
, '['
, ']'
.
A sequence is valid if it follows any one of the following rule:
His brother played with the sequence and misplaced some of the characters, those misplaced characters are denoted by '?' in string A.
Inorder to make the sequence valid again, he decided to replace the character '?'.
Your task is to determing the number of valid sequences that can be created by replacing '?'. Since the answer could be large output answer % 109 + 7.
2 <= |A| <= 150
Length of string A is always even.
First and only argument is a string A.
Return an integer denoting the number of valid sequences.
Input 1:
A = "??}(??"
Input 2:
A = "]???"
Output 1:
3
Output 2:
0
Explanation 1:
Explanation 2:
NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a question? Checkout Sample Codes for more details.