97. Interleaving String
第一个思路是用recursion，不过TLE了，看来是用DP来做了，用DP也算是做出来了，不过有点小疑问，在检查s3的时候，要从1号位开始检查，而不是从0号位，可以考虑成，s3[0]在初始化的时候已经被初始化过了，umm，反正感觉有点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)]
