Python solution with detailed explanation


  • 0
    G

    Solution

    Interleaving String https://leetcode.com/problems/interleaving-string/

    Solving with 3D Memoization Pattern

    • Parameterize the problem in terms of i, j, and k. This means that we have been able to interleave s1[:i], s2[:j], and s3[:k] and would like to determine if we can interleave s1[i:], s2[j:], and s3[k:]
    from collections import defaultdict
    class Solution(object):
        def helper(self, s1, s2, s3, i, j, k, cache):
            M, N, P = len(s1), len(s2), len(s3)
            if i == M and j == N and k == P:
                return True
            elif M+N-i-j != P-k:
                return False
            elif (i in cache) and (j in cache[i]) and (k in cache[i][j]):
                return cache[i][j][k]
            else:
                cache[i].setdefault(j, {}).setdefault(k, False)
                if i < M and j < N and s1[i] != s3[k] and s2[j] != s3[k]:
                    cache[i][j][k] = False
                elif i < M and j < N and s1[i] == s3[k] and s2[j] == s3[k]:
                    cache[i][j][k] = self.helper(s1, s2, s3, i+1, j, k+1, cache) or self.helper(s1, s2, s3, i, j+1, k+1, cache)
                elif i < M and s1[i] == s3[k]:
                    cache[i][j][k] = self.helper(s1, s2, s3, i+1, j, k+1, cache)
                elif j < N and s2[j] == s3[k]:
                    cache[i][j][k] = self.helper(s1, s2, s3, i, j+1, k+1, cache)
                return cache[i][j][k]
        
        def isInterleave(self, s1, s2, s3):
            """
            :type s1: str
            :type s2: str
            :type s3: str
            :rtype: bool
            """
            if len(s3) != len(s1) + len(s2):
                return False
            cache = defaultdict(dict)
            return self.helper(s1, s2, s3, 0, 0, 0, cache)
    

    Solving with 2 parameters

    • Do we really need 3 parameters? k must be equal to i+j at all times. This means it is not a free parameter and can be eliminated.
    from collections import defaultdict
    class Solution1(object):
        def helper(self, s1, s2, s3, i, j, k, cache):
            M, N, P = len(s1), len(s2), len(s3)
            if i == M and j == N and k == P:
                return True
            elif (i in cache) and (j in cache[i]):
                return cache[i][j]
            else:
                if i < M and j < N and s1[i] != s3[k] and s2[j] != s3[k]:
                    cache[i][j] = False
                elif i < M and j < N and s1[i] == s3[k] and s2[j] == s3[k]:
                    cache[i][j] = self.helper(s1, s2, s3, i+1, j, k+1, cache) or self.helper(s1, s2, s3, i, j+1, k+1, cache)
                elif i < M and s1[i] == s3[k]:
                    cache[i][j] = self.helper(s1, s2, s3, i+1, j, k+1, cache)
                elif j < N and s2[j] == s3[k]:
                    cache[i][j] = self.helper(s1, s2, s3, i, j+1, k+1, cache)
                return cache[i][j]
        
        def isInterleave(self, s1, s2, s3):
            """
            :type s1: str
            :type s2: str
            :type s3: str
            :rtype: bool
            """
            if len(s3) != len(s1) + len(s2):
                return False
            cache = dd = defaultdict(lambda: defaultdict(bool))
            return self.helper(s1, s2, s3, 0, 0, 0, cache)
    

Log in to reply
 

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