97. Recursive, Python, Interleaving String


  • 0
    S

    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:
                          visited.add((i+1,j))
                          if inter(i+1,j, visited):return True 
    
                   if j<l2 and s2[j]==s3[i+j] and (i,j+1) not in visited:
                         visited.add((i,j+1))
                         if inter(i,j+1,visited): return True
            
                   return False 
    
        l1=len(s1);l2=len(s2);l3=len(s3)
        if l1+l2!=l3: return False 
        return inter(0,0,set((0,0)))

  • 0
    B

    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.