Friday, September 19, 2014

Leetcode: Interleaving String @Python

class Solution:
    # @return a boolean
    def isInterleave(self, s1, s2, s3):
        n=len(s1)
        m=len(s2)
        l=len(s3)
        if l!=n+m:return False
        match=[[True]*(m+1) for i in range(n+1)]
        for i in range(1,n+1):
            match[i][0]=match[i-1][0] and s1[i-1]==s3[i-1]
        for j in range(1,m+1):
            match[0][j]=match[0][j-1] and s2[j-1]==s3[j-1]
        for i in range(1,n+1):
            for j in range(1,m+1):
                match[i][j]=(s3[i+j-1]==s1[i-1] and match[i-1][j]) or (s3[i+j-1]==s2[j-1] and match[i][j-1])
        return match[n][m]

No comments :

Post a Comment