Simple Python with memo beats 97%

  • 0

    Here I use i, j, k to represent the corresponding indices of strings s1, s2, s3. Then it's very straight forward.

    class Solution(object):
        def isInterleave(self, s1, s2, s3):
            :type s1: str
            :type s2: str
            :type s3: str
            :rtype: bool
            def helper(i,j,k):
                if k == n3: return True
                if (i, j, k) not in memo:
                    memo[(i, j, k)] = (i < n1 and s3[k] == s1[i] and helper(i+1, j, k+1)) or \
                                      (j < n2 and s3[k] == s2[j] and helper(i, j+1, k+1))
                return memo[(i, j, k)]
            n1, n2, n3 = len(s1), len(s2), len(s3)
            memo = {}
            return n1 + n2 == n3 and helper(0,0,0)

Log in to reply

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