# O(m*n) space
def isInterleave1(self, s1, s2, s3):
r, c, l= len(s1), len(s2), len(s3)
if r+c != l:
return False
dp = [[True for _ in xrange(c+1)] for _ in xrange(r+1)]
for i in xrange(1, r+1):
dp[i][0] = dp[i1][0] and s1[i1] == s3[i1]
for j in xrange(1, c+1):
dp[0][j] = dp[0][j1] and s2[j1] == s3[j1]
for i in xrange(1, r+1):
for j in xrange(1, c+1):
dp[i][j] = (dp[i1][j] and s1[i1] == s3[i1+j]) or \
(dp[i][j1] and s2[j1] == s3[i1+j])
return dp[1][1]
# O(2*n) space
def isInterleave2(self, s1, s2, s3):
l1, l2, l3 = len(s1)+1, len(s2)+1, len(s3)+1
if l1+l2 != l3+1:
return False
pre = [True for _ in xrange(l2)]
for j in xrange(1, l2):
pre[j] = pre[j1] and s2[j1] == s3[j1]
for i in xrange(1, l1):
cur = [pre[0] and s1[i1] == s3[i1]] * l2
for j in xrange(1, l2):
cur[j] = (cur[j1] and s2[j1] == s3[i+j1]) or \
(pre[j] and s1[i1] == s3[i+j1])
pre = cur[:]
return pre[1]
# O(n) space
def isInterleave3(self, s1, s2, s3):
r, c, l= len(s1), len(s2), len(s3)
if r+c != l:
return False
dp = [True for _ in xrange(c+1)]
for j in xrange(1, c+1):
dp[j] = dp[j1] and s2[j1] == s3[j1]
for i in xrange(1, r+1):
dp[0] = (dp[0] and s1[i1] == s3[i1])
for j in xrange(1, c+1):
dp[j] = (dp[j] and s1[i1] == s3[i1+j]) or (dp[j1] and s2[j1] == s3[i1+j])
return dp[1]
# DFS
def isInterleave4(self, s1, s2, s3):
r, c, l= len(s1), len(s2), len(s3)
if r+c != l:
return False
stack, visited = [(0, 0)], set((0, 0))
while stack:
x, y = stack.pop()
if x+y == l:
return True
if x+1 <= r and s1[x] == s3[x+y] and (x+1, y) not in visited:
stack.append((x+1, y)); visited.add((x+1, y))
if y+1 <= c and s2[y] == s3[x+y] and (x, y+1) not in visited:
stack.append((x, y+1)); visited.add((x, y+1))
return False
# BFS
def isInterleave(self, s1, s2, s3):
r, c, l= len(s1), len(s2), len(s3)
if r+c != l:
return False
queue, visited = [(0, 0)], set((0, 0))
while queue:
x, y = queue.pop(0)
if x+y == l:
return True
if x+1 <= r and s1[x] == s3[x+y] and (x+1, y) not in visited:
queue.append((x+1, y)); visited.add((x+1, y))
if y+1 <= c and s2[y] == s3[x+y] and (x, y+1) not in visited:
queue.append((x, y+1)); visited.add((x, y+1))
return False
Python DP solutions (O(m*n), O(n) space), BFS, DFS.



python solution
class Solution(object): def isInterleave(self, s1, s2, s3): if len(s3) != len(s1) + len(s2) : return False last = set() # ((i,j) , (i2,j2)) last.add((1,1)) for i in range(len(s3)): # cal f(i) tmp = set() for (m,n) in last : #(i,j) if m+1 <len(s1) and s3[i] == s1[m+1]: tmp.add((m+1,n)) if n+1 <len(s2) and s3[i] == s2[n+1]: tmp.add((m,n+1)) last = tmp if not last: return False return True

for each char in s3 , we decide it is belong to s1 or s2 .
f(i) : record s3[0:i] nums of prefix in s1 and s2 ; 
ex: s1"aabcc" s2"dbbca" s3: "aadbbcbcac"
f(0) = [(1,0) ] #s3[0] can only use 'a' in s1
f(1) = [(2,0)] # s3[0:2] can only use "aa " in s1
....
if f(i) == None this is f(i) can not interleaving of s1 and s2


@raydai
The difference isstack.pop()
andqueue.pop(0)
In BFS solution, I think it will be better if use deque:
queue, visited = collections.deque([(0, 0)]), set((0, 0)) while queue: x, y = queue.popleft()