Share 2D DP Python, O(n*m)


  • 0
    W
    class Solution(object):
        def isInterleave(self, s1, s2, s3):
            """
            :type s1: str
            :type s2: str
            :type s3: str
            :rtype: bool
            """
            n,m=len(s1),len(s2)
            if len(s3) !=n+m:
                return False
            df=[[False for i in range(n+1)] for j in range(m+1)]
            df[0][0]=True
            for i in range(1,n+1):
                if s1[:i]==s3[:i]:
                    df[0][i]=True
                else:
                    break
            for i in range(1,m+1):
                if s2[:i]==s3[:i]:
                    df[i][0]=True
                else:
                    break
            for i in range(1,m+1):
                for j in range(1,n+1):
                    if (df[i][j-1]==True and s3[i+j-1]==s1[j-1]) or (df[i-1][j]==True and s3[i+j-1]==s2[i-1]):
                        df[i][j]=True
            return df[m][n]

Log in to reply
 

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