Share my dp solution with explanations, 44ms


  • 0
    R

    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


Log in to reply
 

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