Interleaving string implemented in Python

interleave_string.py

def interleave(a, b):
    if len(a) == 0 and len(b) == 0:
        return []
    elif len(a) == 0:
        return [b]
    elif len(b) == 0:
        return [a]

    first = [a[0] + s for s in interleave(a[1:], b)]
    second = [b[0] + s for s in interleave(a, b[1:])]

    return first + second

def interleave_iter(a, b):
    result = [[b[0:i]] for i in range(len(b) + 1)]

    for i in range(len(a)):
        result[0] = [a[0:i + 1]]

        for j in range(1, len(b) + 1):
            first = [s + a[i] for s in result[j]]
            second = [s + b[j - 1] for s in result[j - 1]]
            result[j] = first + second

    return result[len(b)]

def simplified_interleave_iter(a, b):
    result = [[]]
    for i in range(1, len(b) + 1):
        result.append([b[0:i]])

    for i in range(len(a)):
        result[0] = [a[0:i + 1]]

        for j in range(1, len(b) + 1):
            first = []
            for s in result[j]:
                first.append(s + a[i])

            second = []
            for s in result[j - 1]:
                second.append(s + b[j - 1])

            result[j] = first + second

    return result[len(b)]

if __name__ == '__main__':
    print interleave("abc", "13")
    print ""
    print interleave_iter("abc", "13")
    print ""
    print simplified_interleave_iter("abc", "13")