Python 42 ms using DFS and memoization

  • 0

    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
            return False
        return inner(0,0,0)

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.