algorithm - Corrects sequences of parenthesis -

corrects sequences of parentesis can defined recursively:

• the empty string "" correct sequence.
• if "x" , "y" correct sequences, "xy" (the concatenation of x , y) correct sequence.
• if "x" correct sequence, "(x)" correct sequence.
• each correct parentheses sequence can derived using above rules.

given 2 strings s1 , s2. each character in these strings parenthesis, strings not correct sequences of parentheses. interleave 2 sequences form correct parentheses sequence. note 2 different ways of interleaving 2 sequences produce same final sequence of characters. if happens, count each of ways separately.

compute , return number of different ways produce correct parentheses sequence, modulo 10^9 + 7.

example s1 = (() , s2 = ())

corrects sequences of parentheses, s1 (red) , s2(blue)

i don't understand recursive algorithm, x , y mean? , modulo 10^9 + 7?

first, tried defining permutations of s1 , s2 , calculate number of balanced parentheses. way wrong, isn't it?

class interleavingparenthesis:     def countways(self, s1, s2):         sequences = list(self.__exchange(list(s1 + s2)))         corrects = 0          sequence in sequences:             if self.__iscorrect(sequence):                 corrects += 1      def __iscorrect(self, sequence):         s = stack()         balanced = true         = 0          while < len(sequence) , balanced:             if '(' == sequence[i]:                 s.stack(sequence[i])              elif s.isempty():                 balanced = false              else: s.remove()              += 1          if s.isempty() , balanced: return true          else: return false           def __exchange(self, s):             if len(s) <= 0: yield s              else:                 in range(len(s)):                     p in self.__exchange(s[:i] + s[i + 1:]):                         yield [s[i]] + p  class stack:     def __init__(self):         self.items = []      def stack(self, data):         self.items.append(data)      def remove(self):         self.items.pop()      def isempty(self):         return self.items == [] 

here's example shows how recursive property works:

start with:

x = "()()(())" 

through property 2, break further x , y:

x = "()" ; y = "()(())" 

for x, can @ insides property 3.

x = "" 

because of property 1, know valid. y, use property 2 again:

x = "()" y = "(())" 

using same recursion before (property 2, property 1) know x valid. note in code, have go through same process, i'm saving time humans. y, use property 3:

x = "()" 

and again.. :

x = "" 

and property 1, know valid.

because sub-parts of "()()(())" valid, "()()(())" valid. that's example of recursion: keep breaking things down smaller problems until solvable. in code, have function call regards smaller part of it, in case, x , y.

as question given, there bit doesn't make sense me. don't how there room doubt in string of parentheses, in image linked. in "((()())())" example, there no way these 2 parentheses not match up: "((()())())". therefore answer there 1 permutation every valid string of parentheses, wrong somehow.

could or else expand on this?