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