97. Recursive, Python, Interleaving String

  • 0

    Many solutions have been posted including DP (e.g., O(n) or O(m*n) space), DFS and BFS. I wrote a recursive one. The idea is to test the next letter if the current letter from either s1 (i.e., s1[i] )or s2 (i.e., s2[j] ) matches the current from s3 (i.e., s3[i+j] ), that is, moving forward to the next one s1[i+1] and/or s2[j+1]. it took around 44ms, 92%.

    Note: the set variable 'visited' is used to cut the unnecessary visits; otherwise, it will be TLEd.

     class Solution(object):
         def isInterleave(self, s1, s2, s3):
               def inter(i,j, visited):
                    if i+j==l3: return True 
                    if i<l1 and s1[i]==s3[i+j] and (i+1,j) not in visited:
                          if inter(i+1,j, visited):return True 
                   if j<l2 and s2[j]==s3[i+j] and (i,j+1) not in visited:
                         if inter(i,j+1,visited): return True
                   return False 
        if l1+l2!=l3: return False 
        return inter(0,0,set((0,0)))

  • 0

    What do you think is the time complexity for this ? Is it O(log(m+n)) ?

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.