# Fastest (40ms ~ 44ms) python solution so far using DFS

• def isInterleave(self, s1, s2, s3):
"""
:type s1: str
:type s2: str
:type s3: str
:rtype: bool
"""
if len(s1) + len(s2) != len(s3):
return False

self.visited = set()
return self.search(s1, s2, s3, 0, 0)

def search(self, s1, s2, s3, i1, i2):
if i1 + i2 == len(s3):
return True
else:
if i1 < len(s1) and s1[i1] == s3[i1 + i2] and (i1+1, i2) not in self.visited and self.search(s1, s2, s3, i1+1, i2):
return True

if i2 < len(s2) and s2[i2] == s3[i1 + i2] and (i1, i2+1) not in self.visited and self.search(s1, s2, s3, i1, i2+1):
return True

return False

i1 and i2 are representing the position of each string we want to check against the s3 string.

• class Solution(object):
def isInterleave(self, s1, s2, s3):
"""
:type s1: str
:type s2: str
:type s3: str
:rtype: bool
"""
if len(s1)+len(s2) != len(s3): return False
if len(s1) < len(s2): return self.isInterleave(s2, s1, s3)
dp = [True] * (len(s2) + 1)
for i in range(1, len(s2) + 1):
dp[i] = dp[i-1] and s2[i-1] == s3[i-1]

for i in range(1, len(s1) + 1):
dp[0] = dp[0] and s1[i-1] == s3[i-1]
for j in range(1, len(s2) + 1):
dp[j] =  ( dp[j] and s1[i-1] == s3[i + j -1] ) or ( dp[j - 1] and s2[j-1] == s3[i + j -1] )

return dp[len(s2)]

• Time Complexity: O(n^2); Space Complexity: O(n).
It also beats 99% submission in terms of Run Time. (44ms)

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