class Solution(object):

def isInterleave(self, s1, s2, s3):

if len(s1)>len(s2): #make s1 the shorter string

s1,s2=s2,s1

if not s1:

return s2==s3 # if s1 is empty, compare s2 with s3

n1,n2,n3=len(s1),len(s2),len(s3)

if n1+n2!=n3: # make sure the length is right

return False

dp=set([(0,0)])

for c in s3: #use dp to remember the combinations of s1 and s2 up to chararctor c

newdp=set()

for x,y in dp:

if x<n1 and s1[x]==c:

newdp.add((x+1,y))

if y<n2 and s2[y]==c:

newdp.add((x,y+1))

if not newdp:

return False

dp=newdp

else:

return True