LeetCode 97 Interleaving String - Implementation

2D DP. Check both extension options.

def isInterleave(s1, s2, s3): m, n = len(s1), len(s2) if m + n != len(s3): return False dp = [[False] * (n + 1) for _ in range(m + 1)] dp[0][0] = True

for i in range(m + 1):
    for j in range(n + 1):
        if i > 0 and s1[i-1] == s3[i+j-1]:
            dp[i][j] = dp[i][j] or dp[i-1][j]
        if j > 0 and s2[j-1] == s3[i+j-1]:
            dp[i][j] = dp[i][j] or dp[i][j-1]

return dp[m][n]

$O(m \times n)$ time and space.