O(n^2) time and O(n) space DP solution, python


  • 0
    B

    basic observation is given i and j lengths for s1, s2. we check if s3[i+j-1] equals to the end of s1 or s2. then we can recursively determine if s3[j+i-1] is interleaved from s1, s2 or not

    class Solution:
    # @return a boolean
    def isInterleave(self, s1, s2, s3):
        # using DP:
        len1=len(s1)
        len2=len(s2)
        len3=len(s3)
    
        if len3!=(len1+len2):
            return False
    
        if len3==0:
            return True
    
        DPmatrixold=[False for _ in range(len1+1)]
    
        DPmatrixold[0]=True
    
        for i in range(1,len1+1):
            DPmatrixold[i]=DPmatrixold[i-1] and s3[i-1]==s1[i-1]
    
        DPmatrix=DPmatrixold[:]
    
        for i in range(1,len2+1):
            DPmatrix[0]=(s3[i-1]==s2[i-1])
            for j in range(1,len1+1):
                lastword=s3[i+j-1]
                flag1=False
                flag2=False
                if s1[j-1]==lastword:
                    flag1=DPmatrix[j-1]
                if s2[i-1]==lastword:
                    flag2=DPmatrixold[j]
                DPmatrix[j]=(flag1 or flag2)
            DPmatrixold=DPmatrix[:]
    
    
    
        return DPmatrix[len1]

Log in to reply
 

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