Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.
class Solution(object):
def isInterleave(self, s1, s2, s3):
"""
:type s1: str
:type s2: str
:type s3: str
:rtype: bool
"""
len_s1 = len(s1)
len_s2 = len(s2)
len_s3 = len(s3)
if len_s1 + len_s2 != len_s3:
return False
is_inter_leave = [[True for i in xrange(len_s1+1)] for j in xrange(len_s2+1)]
for i in xrange(1,len_s1+1):
is_inter_leave[0][i] = is_inter_leave[0][i-1] and s1[i-1] == s3[i-1]
for j in xrange(1,len_s2+1):
is_inter_leave[j][0] = is_inter_leave[j-1][0] and s2[j-1] == s3[j-1]
for i in xrange(1,len_s2+1):
for j in xrange(1,len_s1+1):
is_inter_leave[i][j] = (is_inter_leave[i-1][j] and s2[i-1] == s3[i+j-1]) or (is_inter_leave[i][j-1] and s1[j-1] == s3[i+j-1])
return is_inter_leave[len_s2][len_s1]
扫一扫
639
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
