1def is_interleave(s1, s2, s3):
2 m, n = len(s1), len(s2)
3 if m + n != len(s3):
4 return False
5 dp = [[False] * (n + 1) for _ in range(m + 1)]
6 dp[0][0] = True
7 for r in range(1, m + 1):
8 dp[r][0] = dp[r - 1][0] and s1[r - 1] == s3[r - 1]
9 for c in range(1, n + 1):
10 dp[0][c] = dp[0][c - 1] and s2[c - 1] == s3[c - 1]
11 for r in range(1, m + 1):
12 for c in range(1, n + 1):
13 match_s1 = dp[r - 1][c] and s1[r - 1] == s3[r + c - 1]
14 match_s2 = dp[r][c - 1] and s2[c - 1] == s3[r + c - 1]
15 dp[r][c] = match_s1 or match_s2
16 return dp[m][n]