Solutions

# Top down or bottom up DP. 2 choices: pick one char from s1 or pick one char from s2.
# dp


# Top-down DP - O(l1*l2) time, O(l1*l2) space
def isInterleave1(s1: str, s2: str, s3: str) -> bool:
    if len(s3) != len(s1) + len(s2):
        return False

    dp = {}

    # Is it possible to build s3[i3:] using s1[i1:] nad s2[i2:]?
    def dfs(i1: int, i2: int, i3: int) -> bool:
        if i3 == len(s3):
            return i1 == len(s1) and i2 == len(s2)
        if (i1,i2) in dp:
            return dp[(i1,i2)]

        res = False
        if i1 < len(s1) and s1[i1] == s3[i3]:
            res |= dfs(i1+1, i2, i3+1)
        if i2 < len(s2) and s2[i2] == s3[i3]:
            res |= dfs(i1, i2+1, i3+1)

        dp[(i1,i2)] = res
        return res

    return dfs(0, 0, 0)


# Bottom-up DP - O(l1*l2) time, O(l1*l2) space
def isInterleave(s1: str, s2: str, s3: str) -> bool:
    if len(s3) != len(s1) + len(s2):
        return False

    # dp[i][j] is True if s3[i+j:] can be made with s1[i:] and s2[j:]
    dp = [[False] * (len(s2)+1) for _ in range(len(s1)+1)]
    # NB: s2 is for columns, s1 for rows (after)

    # base case: s3[len(s1)+len(s2):], which is an empty str, can be made of two empty str
    dp[len(s1)][len(s2)] = True

    for i in range(len(s1) , -1, -1):
        for j in range(len(s2), -1, -1):
            if i < len(s1) and s1[i] == s3[i+j] and dp[i+1][j]:
                dp[i][j] = True
            if j < len(s2) and s2[j] == s3[i+j] and dp[i][j+1]:
                dp[i][j] = True

    return dp[0][0]


# Alternative top down DP with lru_cache - O(l1*l2) time, O(l1*l2) space
from functools import lru_cache
@lru_cache()
def isInterleave2(s1: str, s2: str, s3: str) -> bool:
    if s1 == s2 == s3 == '':
        return True
    elif s3 == '' and (s1 != '' or s2 != ''):
        return False
    
    if s1 == '':
        return s2 == s3
    elif s2 == '':
        return s1 == s3
    
    if s1[0] == s2[0] == s3[0]:
        return self.isInterleave(s1[1:] , s2, s3[1:]) or self.isInterleave(s1 , s2[1:], s3[1:])
    elif s1[0] == s3[0]:
        return self.isInterleave(s1[1:] , s2, s3[1:])
    elif s2[0] == s3[0]:
        return self.isInterleave(s1 , s2[1:], s3[1:])
    else:
        return False