NO LOOPS, Quick-n-easy 5-liner in Python, beats 99%

  • 1

    Pure recursion without loops. Useful for interviews when we need to code things fast without much bullcrap. Shortest in Python I've seen so far for this problem, but may be wrong.

    class Solution(object):
        def isInterleave(self, s1, s2, s3, memo={}):
            if len(s1) + len(s2) != len(s3): return False
            if not s1 and not s2 and not s3: return True
            if (s1, s2, s3) in memo:         return memo[s1, s2, s3]
            memo[s1,s2,s3] =\
                   (len(s1) > 0 and len(s3) > 0 and s1[0] == s3[0] and self.isInterleave(s1[1:], s2, s3[1:], memo)) or\
                   (len(s2) > 0 and len(s3) > 0 and s2[0] == s3[0] and self.isInterleave(s1, s2[1:], s3[1:], memo))
            return memo[s1,s2,s3]
    # 101 / 101 test cases passed.
    # Status: Accepted
    # Runtime: 44 ms

  • 0

    Using decorator we could have a general way to add cache to any recursion function.

Log in to reply

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