Python 3 (Recursion+Memoization)


#1
mapper = {}
def processval(A,B,C,ind_A,ind_B,ind_C):
   if ind_C>=len(C): 
       if ind_A>=len(A) and ind_B>=len(B):
           return True
       else:
           return False
   string_key = str(ind_A)+"-"+str(ind_A)+"-"+str(ind_C)
   if mapper.get(string_key):
       return mapper[string_key]

   if ind_A<len(A) and ind_B<len(B) and C[ind_C]==A[ind_A] and C[ind_C]==B[ind_B]:
       mapper[string_key] = processval(A,B,C,ind_A+1,ind_B,ind_C+1) or 
processval(A,B,C,ind_A,ind_B+1,ind_C+1)
       return mapper[string_key]    
   elif ind_A<len(A) and C[ind_C]==A[ind_A]:
       mapper[string_key] = processval(A,B,C,ind_A+1,ind_B,ind_C+1)
       return mapper[string_key] 
   elif ind_B<len(B) and C[ind_C]==B[ind_B]:
       mapper[string_key] = processval(A,B,C,ind_A,ind_B+1,ind_C+1)
       return mapper[string_key] 
   else:
       return False

class Solution:
# @param A : string
# @param B : string
# @param C : string
# @return an integer

def isInterleave( self,A, B, C):
    global mapper
    mapper = {}
    if len(A)+len(B)!=len(C):
        return 0

    return 1 if processval(A,B,C,0,0,0) else 0