AC simple recursive python solution beating 95% of submissions


  • 0
    I
    def isInterleave(self, a, b, c):
        c_len = len(c)
        b_len = len(b)
        a_len = len(a)
        
        if a_len + b_len != c_len: return False
        
        visited = set()
        
        def recurse(a_i, b_i, c_i):
            if tuple([a_i, b_i, c_i]) in visited: return False
            visited.add(tuple([a_i, b_i, c_i]))
            if a_i == a_len and b_i == b_len and c_i == c_len: return True
            if a_i < a_len and a[a_i] == c[c_i] and recurse(a_i+1, b_i, c_i+1): return True
            if b_i < b_len and b[b_i] == c[c_i] and recurse(a_i, b_i+1, c_i+1): return True
            return False
        
        return recurse(0,0,0)

Log in to reply
 

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