classSolution: """ @params s1, s2, s3: Three strings as description. @return: return True if s3 is formed by the interleaving of s1 and s2 or False if not. @hint: you can use [[True] * m for i in range (n)] to allocate a n*m matrix. """ defisInterleave(self, s1, s2, s3): len1 = 0if s1 isNoneelselen(s1) len2 = 0if s2 isNoneelselen(s2) len3 = 0if s3 isNoneelselen(s3)
if len3 != len1 + len2: returnFalse
i1, i2 = 0, 0 for i3 in xrange(len(s3)): result = False if (i1 < len1 and s1[i1] == s3[i3]) and \ (i1 < len1 and s1[i1] == s3[i3]): # s1[1+i1:], s2[i2:], s3[1+i3:] case1 = self.isInterleave(s1[1 + i1:], s2[i2:], s3[1 + i3:]) # s1[i1:], s2[1+i2:], s3[1+i3:] case2 = self.isInterleave(s1[i1:], s2[1 + i2:], s3[1 + i3:]) return case1 or case2
if i1 < len1 and s1[i1] == s3[i3]: i1 += 1 result = True continue
if i2 < len2 and s2[i2] == s3[i3]: i2 += 1 result = True continue
# return instantly if both s1 and s2 can not pair with s3 ifnot result: returnFalse
classSolution { public: /** * Determine whether s3 is formed by interleaving of s1 and s2. * @param s1, s2, s3: As description. * @return: true of false. */ boolisInterleave(string s1, string s2, string s3){ int len1 = s1.size(); int len2 = s2.size(); int len3 = s3.size();
classSolution: """ @params s1, s2, s3: Three strings as description. @return: return True if s3 is formed by the interleaving of s1 and s2 or False if not. @hint: you can use [[True] * m for i in range (n)] to allocate a n*m matrix. """ defisInterleave(self, s1, s2, s3): len1 = 0if s1 isNoneelselen(s1) len2 = 0if s2 isNoneelselen(s2) len3 = 0if s3 isNoneelselen(s3)
if len3 != len1 + len2: returnFalse
f = [[True] * (1 + len2) for i in xrange (1 + len1)] # s1[i1 - 1] == s3[i1 + i2 - 1] && f[i1 - 1][i2] for i in xrange(1, 1 + len1): f[i][0] = s1[i - 1] == s3[i - 1] and f[i - 1][0] # s2[i2 - 1] == s3[i1 + i2 - 1] && f[i1][i2 - 1] for i in xrange(1, 1 + len2): f[0][i] = s2[i - 1] == s3[i - 1] and f[0][i - 1] # i1 >= 1, i2 >= 1 for i1 in xrange(1, 1 + len1): for i2 in xrange(1, 1 + len2): case1 = s1[i1 - 1] == s3[i1 + i2 - 1] and f[i1 - 1][i2] case2 = s2[i2 - 1] == s3[i1 + i2 - 1] and f[i1][i2 - 1] f[i1][i2] = case1 or case2
classSolution { public: /** * Determine whether s3 is formed by interleaving of s1 and s2. * @param s1, s2, s3: As description. * @return: true of false. */ boolisInterleave(string s1, string s2, string s3){ int len1 = s1.size(); int len2 = s2.size(); int len3 = s3.size();