# Python 42 ms using DFS and memoization

• 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 `s3`.

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 `s1` and `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 `s2` and `s3`. If neither are the case, then we return false.

For example:
`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[0] == s1[0] and isInterleave(s1[1:], s2, s3[1:]):
return True
if s3[0] == s2[0]  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