Python Memo(O 2^N)

Our recursive/memoized answer should be rated as an easy question.

There are three variables, i, j, k for the current index of s1, s2, and s3 respectively.

Either s1[i] == s3[k] or s2[j] == s3[k] otherwise it's immediately false because the formed string is a sequence and must be consecutive and not a subsequence.

In the case that s1[i] == s2[j], we need to try out both ways.

Thus the worst case is 2^N as there can possibly be two choices at every letter of s3.

Thus, S3[k] == S1[i] and recur(i+1, j, k+1) or S3[k] == S2[j] and recur(i, j+1, k+1), must reach the end, otherwise False.

```
class Solution(object):
def isInterleave(self, s1, s2, s3):
if len(s1) + len(s2) != len(s3):
return False
return self.can(s1, s2, s3, dict())
def can(self, s1, s2, s3, cache):
if len(s1) == 0 and len(s2) == 0 and len(s3) == 0:
return True
if len(s3) == 0:
return False
if (s1, s2, s3) in cache:
return cache[(s1, s2, s3)]
take_s1 = False
take_s2 = False
if len(s1) > 0 and s1[0] == s3[0]:
take_s1 = self.can(s1[1:], s2, s3[1:], cache)
if len(s2) > 0 and s2[0] == s3[0]:
take_s2 = self.can(s1, s2[1:], s3[1:], cache)
cache[(s1,s2,s3)] = take_s1 or take_s2
return cache[(s1,s2,s3)]
```

Python Tabulate: O(len(s1) * len(s2)

Our tabulated DP answer is a little trickier, but follows the same properties as other string matching questions.

We have to form a table of i+1 * j+1 length where i and j corresponds to the length of s1 and s2

and s1[i-1] is the current letter in i and s2[j-1] is the current letter in j so that our dp table can account for empty strings.

Note that i+j-1 is the character k that we want to match in S3.

Our base case is that dp[0][0] == True because if we have no elements from either string, we form the empty string.

Next, we need to consider what it means if j == 0 or i == 0. This means that we are only taking from one string, thus if j == 0: look at if s1[i] matches s3[i] and so forth.

Our tricky case is if i>0 and j>0. We need to look at if dp[i-1][j] is True or dp[i][j-1] is True and if so, the newly added letter is also == the new length of s3.

```
class Solution(object):
def isInterleave(self, s1, s2, s3):
if len(s1) == 0:
return s2 == s3
if len(s2) == 0:
return s1 == s3
if len(s3) != len(s1) + len(s2):
return False
dp = [[None for i in range(len(s2)+1)] for j in range(len(s1)+1)]
for i in range(len(dp)):
for j in range(len(dp[0])):
if i == 0 and j == 0:
dp[i][j] = True
elif i == 0:
dp[i][j] = dp[i][j-1] and s2[j-1] == s3[j-1]
elif j == 0:
dp[i][j] = dp[i-1][j] and s1[i-1] == s3[i-1]
else:
if dp[i-1][j] == True and s3[i+j-1] == s1[i-1]:
dp[i][j] = True
elif dp[i][j-1] == True and s3[i+j-1] == s2[j-1]:
dp[i][j] = True
else:
dp[i][j] = False
return dp[-1][-1]
```