原題
給出三個字符串:s1悔叽、s2、s3祖很，判斷s3是否由s1和s2交叉構(gòu)成壮啊。
樣例
比如 s1 =** "aabcc"** s2 =** "dbbca"**
- 當 s3 = "aadbbcbcac"，返回 true.
- 當 s3 = "aadbbbaccc"产上， 返回 false.
解題思路
- 典型序列型動態(tài)規(guī)劃棵磷，Two Sequence DP
- 狀態(tài)cache[i][j]表示，s1的前i個字符和s2的前j個字符是否能交叉構(gòu)成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)]
