InterleavingParenthesis
SRM 718 · 2017-05-20 · by lg5293
Problem Statement
Correct parentheses sequences can be defined recursively as follows:
- The empty string "" is a correct sequence.
- If "X" and "Y" are correct sequences, then "XY" (the concatenation of X and Y) is a correct sequence.
- If "X" is a correct sequence, then "(X)" is a correct sequence.
- Each correct parentheses sequence can be derived using the above rules.
Examples of correct parentheses sequences include "", "()", "()()()", "(()())", and "(((())))".
You are given two
You would like to interleave the two sequences so that they will form a correct parentheses sequence. Note that sometimes two different ways of interleaving the two sequences will produce the same final sequence of characters. Even if that happens, we count each of the ways separately. (See Example 0 for a clarification.)
Compute and return the number of different ways to produce a correct parentheses sequence, modulo 10^9 + 7.
Constraints
- s1,s2 will contain between 1 and 2,500 characters, inclusive.
- Each character of s1,s2 will be '(' or ')'.
"(()" "())" Returns: 19
The 19 ways are: Here, the red characters come from the first sequence, and the blue characters come from the second sequence.
")"
"("
Returns: 1
"((((("
")))))"
Returns: 42
"()(()" "))((())" Returns: 10
"()()()()()()()()()()()()()()()()()()()()" "()()()()()()()()()()()()()()()()()" Returns: 487340184
Don't forget about the mod.
Submissions are judged against all 93 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class InterleavingParenthesis with a public method int countWays(string s1, string s2) · 93 test cases · 2 s / 256 MB per case