# Python solution with detailed explanation

• 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)

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