Interleaving String less than 1 minute read 97. Interleaving String 1D dynamic programming Note that there is no need to have another memo array as it is updated exactly from left to right. class Solution: def isInterleave(self, s1: str, s2: str, s3: str) -> bool: l1, l2, l3 = len(s1), len(s2), len(s3) if l3 != l1 + l2: return False if l1 == 0: return s2 == s3 if l2 == 0: return s1 == s3 memo = [] memo = [False for _ in range(l2+1)] memo[0] = True for i2 in range(1, l2+1): memo[i2] = memo[i2-1] and s2[i2-1] == s3[i2-1] for i1 in range(1, l1+1): memo[0] = memo[0] and s1[i1-1] == s3[i1-1] for i2 in range(1, l2+1): i3 = i1 + i2 memo[i2] = (memo[i2] and s1[i1-1]==s3[i3-1]) or (memo[i2-1] and s2[i2-1]==s3[i3-1]) return memo[-1] Twitter Facebook LinkedIn Previous Next Comments
Comments