There may be a duplicate somewhere, but I found my solution to be pretty compact and it seems to run fairly well!
The general idea is that we will recursively chomp our strings until we work our way to the base case. The base case isn't so bad: if we run out of one of our strings, we know they are interleaved if the remainder of the other string is equal to the remainder of
The intermediary steps in my recursion just check if the first character of
s1 is the first character of
s3 and if that is the case we also check the recursive call
inner(s1[1:], s2, s3[1:]), cutting off both the first character of
s3. If the recursion returns
True, we know there is something in my sub-tree that says I can be interleaved, so we early return
True. We do a similar check against
s3. If neither are the case, then we return false.
s1: "ab", s2: "cd", s3: "acbd"
we compare s1 and s3 and see that they both start with "a", so we recurse on
("b", "cd, "acbd")
s1: "b", s2: "cd", s3: "cbd"
we compare s1 and s3 and see that "b" is not "c", so
we compare s2 and s3 and see that they both start with "c"
s1: "b", s2: "d", s3: "bd"
and so on...
My first solution which failed from timeouts:
def isInterleave(s1, s2, s3): if len(s1) == 0: return s2 == s3 if len(s2) == 0: return s1 == s3 if s3 == s1 and isInterleave(s1[1:], s2, s3[1:]): return True if s3 == s2 and isInterleave(s1, s2[1:], s3[1:]): return True return False
So I thought what improvements can I make?
Well you'll notice that I am doing a lot of slices in my recursive section. This is a fairly expensive operation, both in time and space, so instead my first optimization was to pass in indexes to my current position in the string instead. Now, I will check the value at the current index for i, j, and k instead of checking the first characters of s1, s2, and s3. My base case also checks if
len(s1) == i instead of
len(s1) == 0, for example.
The other optimization I need to make is that this algorithm builds a pretty bulky tree in the worst case, and I've done no work to memoize it. So, we'll make a cache that stores if we've encountered a tuple (i, j, k) that cannot be interleaved. This should take care of the overlapping subproblems! We can use a
set() and add tuples (i, j, k) when we find they are not interleavable.
def isInterleave(s1, s2, s3): # Set gives fast membership check, so we will memoize # which code paths are dead-ends. rejects = set() def inner(i, j, k): # If we have run out of one string, we know they # are interleaved if the remainder of the other # two strings are equal. if len(s1) == i: return s2[j:] == s3[k:] if len(s2) == j: return s1[i:] == s3[k:] # Check our cache of bad values if (i,j,k) in rejects: return False # If the first character of the substr we're considering # is equal, then we check the recursive state space if s3[k] == s1[i] and inner(i+1,j,k+1): return True if s3[k] == s2[j] and inner(i,j+1,k+1): return True # Now we're in the land of failure and we make sure # to save our failed result for fast lookup rejects.add((i,j,k)) return False return inner(0,0,0)