97. Interleaving String
第一個思路是用recursion榨了，不過TLE了煎谍，看來是用DP來做了，用DP也算是做出來了龙屉，不過有點(diǎn)小疑問呐粘，在檢查s3的時候，要從1號位開始檢查转捕，而不是從0號位作岖，可以考慮成，s3[0]在初始化的時候已經(jīng)被初始化過了五芝，umm鳍咱，反正感覺有點(diǎn)tricky
class Solution(object):
def isInterleave(self, s1, s2, s3):
"""
:type s1: str
:type s2: str
:type s3: str
:rtype: bool
"""
print s1, s2, s3
if len(s3) != len(s1) + len(s2):
return False
if not s1 and not s2 and not s3:
return True
if not s1:
return s2 == s3
if not s2:
return s1 == s3
if s1[0] == s2[0]:
if s3[0] == s1[0]:
return self.isInterleave(s1[1:], s2, s3[1:]) or self.isInterleave(s1, s2[1:], s3[1:])
else:
return False
elif s1[0] == s3[0]:
return self.isInterleave(s1[1:], s2, s3[1:])
elif s2[0] == s3[0]:
return self.isInterleave(s1, s2[1:], s3[1:])
else:
return False
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
if not s1 and not s2 and not s3:
return True
if not s1:
return s2 == s3
if not s2:
return s1 == s3
# dp[i][j] 表示 s1 0~i s2 0~j是否可以
dp = [[False for _ in range(len(s2)+1)] for _ in range(len(s1)+1)]
dp[0][0] = True
for i in range(1, len(s1)+1):
if s1[i-1] == s3[i-1]:
dp[i][0] = True
else:
break
for i in range(1, len(s2)+1):
if s2[i-1] == s3[i-1]:
dp[0][i] = True
else:
break
for i in range(1, len(s1)+1):
for j in range(1, len(s2)+1):
if not dp[i][j]:
if s1[i-1] == s3[i+j-1] == s2[j-1]:
dp[i][j] = dp[i-1][j] or dp[i][j-1]
elif s1[i-1] == s3[i+j-1]:
dp[i][j] = dp[i-1][j]
elif s3[i+j-1] == s2[j-1]:
dp[i][j] = dp[i][j-1]
return dp[len(s1)][len(s2)]
