JOIN

 Problem Statement

Problem Statement for InterleavingParenthesis

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

0)

 `"(()"` `"())"`
`Returns: 19`
 The 19 ways are: Here, the red characters come from the first sequence, and the blue characters come from the second sequence.
1)

 `")"` `"("`
`Returns: 1`
2)

 `"((((("` `")))))"`
`Returns: 42`
3)

 `"()(()"` `"))((())"`
`Returns: 10`
4)

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