DP in python with explaination


  • 0

    c1,c2,c3 as the pointer to s1,s2,s3
    if c1 is ok and c2 is ok, choose c1 first,keep going
    if stucked, suppose j in s3, find all s3[j] in (c2,min(len(s2),c2+c1+j) save in list p
    for every position in p, dp check
    s1[:c1-c2+j] , s2[:j], s3[:c3] are Ture
    and s1[c1-c2+j],s2[j],s3[c3] are True

    class Solution(object):
        def isInterleave(self, s1, s2, s3):
            """
            :type s1: str
            :type s2: str
            :type s3: str
            :rtype: bool
            """
            c1,c2,c3=0,0,0
            if s1=="":return s2==s3
            elif s2=="":return s1==s3
            elif s3=="":return False
            
            if len(s3)!=len(s1)+len(s2):return False
            for c3 in range(0,len(s3)):
                i=s3[c3]
                if c1<len(s1) and i==s1[c1] :c1+=1
                elif c2<len(s2) and i==s2[c2] :c2+=1
                else:
                    #j=-1
                    jj=[]
                    for x in range(c2+1,min(len(s2),c1+c2+1)):
                        if s2[x]==i:
                            jj.append(x)
                    if len(jj)==0:return False
                    else:
                        for j in jj:
                            if self.isInterleave(s1[:c1-j+c2],s2[:j],s3[:c3]):
                                c1=c1-j+c2
                                c2=j
                                if self.isInterleave(s1[c1:],s2[j+1:],s3[c3+1:]):return True
                        return False
                        #else:return False
            return True
    

Log in to reply
 

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