# [leetcode/lintcode 题解] 阿里算法面试真题：交叉字符串

样例1

"aabcc"
"dbbca"

true
样例2

""
""
"1"

false
样例3

"aabcc"
"dbbca"

false

### 算法：动态规划

class Solution:
"""
@params s1, s2, s3: Three strings as description.
@return: return True if s3 is formed by the interleaving of
s1 and s2 or False if not.
@hint: you can use [[True] * m for i in range (n)] to allocate a n*m matrix.
"""
def isInterleave(self, s1, s2, s3):
if s1 is None or s2 is None or s3 is None:
return False
if len(s1) + len(s2) != len(s3):
return False

interleave = [[False] * (len(s2) + 1) for i in range(len(s1) + 1)]
interleave[0][0] = True
for i in range(len(s1)):
interleave[i + 1][0] = s1[:i + 1] == s3[:i + 1]
for i in range(len(s2)):
interleave[0][i + 1] = s2[:i + 1] == s3[:i + 1]

for i in range(len(s1)):
for j in range(len(s2)):
interleave[i + 1][j + 1] = False
if s1[i] == s3[i + j + 1]:
interleave[i + 1][j + 1] = interleave[i][j + 1]
if s2[j] == s3[i + j + 1]:
interleave[i + 1][j + 1] |= interleave[i + 1][j]
return interleave[len(s1)][len(s2)]

+ 订阅