InterleavingParenthesis | Topcoder Archive

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 Strings s1 and s2. Each character in these strings is a parenthesis, but the strings themselves are not necessarily correct sequences of parentheses.

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.

Definition

Class:: InterleavingParenthesis
Method:: countWays
Parameters:: String, String
Returns:: int
Method signature:: int countWays(String s1, String s2)
(be sure your method is public)

Constraints

s1,s2 will contain between 1 and 2,500 characters, inclusive.
Each character of s1,s2 will be '(' or ')'.

Examples

```
"(()"
```
```
"())"
```
```
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.

```
"(())())))"
```
```
"(())()"
```
```
Returns: 0
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.