原题
给出三个字符串:s1、s2、s3，判断s3是否由s1和s2交叉构成。
样例
比如 s1 =** "aabcc"** s2 =** "dbbca"**
- 当 s3 = "aadbbcbcac"，返回 true.
- 当 s3 = "aadbbbaccc"， 返回 false.
解题思路
- 典型序列型动态规划，Two Sequence DP
- 状态cache[i][j]表示，s1的前i个字符和s2的前j个字符是否能交叉构成s3的前i+j个字符
- 初始化：
- cache[0][0] = True 因为两个空字符串可以组成空字符串
- 边界情况是一个字符串为空，初始化只需判断另一个字符串和目标字符串前x为是否相等
- 递推关系 cache[i][j] = (s1[i] == s3[i+j] and cache[i-1][j]) or (s2[j] == s3[i+j] and cache[i][j-1])
- �最后说一个小小的简化程序的trick
if something > 0 and others < 0:
x = True
# 直接可以写成
x = something > 0 and others < 0
完整代码
class Solution(object):
def isInterleave(self, s1, s2, s3):
"""
:type s1: str
:type s2: str
:type s3: str
:rtype: bool
"""
if len(s3) != len(s1) + len(s2):
return False
cache = [[False for i in range(len(s1) + 1)] for j in range(len(s2) + 1)]
cache[0][0] = True
for i in range(1, len(s1) + 1):
if cache[0][i -1] and s1[i - 1] == s3[i - 1]:
cache[0][i] = True
else:
break
for j in range(1, len(s2) + 1):
if cache[j - 1][0] and s2[j - 1] == s3[j - 1]:
cache[j][0] = True
else:
break
for j in range(1, len(s2) + 1):
for i in range(1, len(s1) + 1):
if (cache[j - 1][i] and s2[j - 1] == s3[j + i - 1]) or (cache[j][i - 1] and s1[i - 1] == s3[j + i - 1]):
cache[j][i] = True
return cache[len(s2)][len(s1)]
