# Python short and concise DP solution O(mn) time

• 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]
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.