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)))