simple python DP


  • 0
    Z
    class Solution(object):
        def isInterleave(self, s1, s2, s3):
            if not s3:
                return (not s1) and (not s2)
            dp = [[None] * len(s2) for i in range(len(s1))]
            def isInterleaveHelper(s1, ind1, s2, ind2, s3, ind3, dp):
                if ind3 == len(s3):
                    return ind1 == len(s1) and ind2 == len(s2)
                elif ind2 >= len(s2):
                    return s1[ind1:] == s3[ind3:]
                elif ind1 >= len(s1):
                    return s2[ind2:] == s3[ind3:]
                elif dp[ind1][ind2] != None:
                    return dp[ind1][ind2]
                elif s3[ind3] != s1[ind1] and s3[ind3] != s2[ind2]:
                    dp[ind1][ind2] = False
                elif s3[ind3] == s1[ind1] and s3[ind3] == s2[ind2]:
                    dp[ind1][ind2] = (isInterleaveHelper(s1, ind1+1, s2, ind2, s3, ind3+1, dp) or 
                        isInterleaveHelper(s1, ind1, s2, ind2+1, s3, ind3+1, dp))
                elif s3[ind3] == s1[ind1]:
                    dp[ind1][ind2] = isInterleaveHelper(s1, ind1+1, s2, ind2, s3, ind3+1, dp)
                else:
                    dp[ind1][ind2] = isInterleaveHelper(s1, ind1, s2, ind2+1, s3, ind3+1, dp)
                return dp[ind1][ind2]
            return isInterleaveHelper(s1, 0, s2, 0, s3, 0, dp)

Log in to reply
 

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