Maintain an `m`

by `n`

matrix `res`

to store the contemporary results, where `m`

and `n`

are the lengths of s1 and s2, respectively.

`res[i][j]`

represents the boolean value whether `s1[0:i]`

and `s2[0:j]`

can form interleaving string `s3[0:i+j]`

,

A recursive relation is hence:

condition1: `res[i-1][j]`

is `True`

and i-th char of `s1`

equals (i+j)th char of `s3`

;

condition2: `res[i][j-1]`

is `True`

and j-th char of `s2`

equals (i+j)th char of `s3`

The validity of either condition 1 or 2 marks `res[i][j]`

as `True`

.

An AC solution is provided as follows. The time complextiy is apparently `O(mn)`

and also the space complexity, while the later one can be optimized to `O(min(m,n))`

.

```
class Solution(object):
def isInterleave(self, s1, s2, s3):
"""
:type s1: str
:type s2: str
:type s3: str
:rtype: bool
"""
if len(s1) + len(s2) != len(s3):
return False
nrow, ncol = len(s1), len(s2)
res = [[None for _ in range(ncol+1)] for _ in range(nrow+1)]
res[0][0] = True
for i in range(1, nrow+1):
res[i][0] = res[i-1][0] and (s1[i-1] == s3[i-1])
for j in range(1, ncol+1):
res[0][j] = res[0][j-1] and (s2[j-1] == s3[j-1])
for i in range(1, nrow+1):
for j in range(1, ncol+1):
bool1 = res[i-1][j] and (s1[i-1] == s3[i+j-1])
bool2 = res[i][j-1] and (s2[j-1] == s3[i+j-1])
res[i][j] = (bool1 or bool2)
return res[nrow][ncol]
```