Если функцию is_merge закэшировать, то получим рекурсию + динамику.
Это гарантируем максимальное время работы за O(N^2) от длины строки

from functools import lru_cache

@lru_cache()
def is_merge(s, part1, part2):
    if part1 == '':
        return s == part2
    if part2 == '':
        return s == part1
    if s == '':
        return False
    return s[0] == part1[0] and is_merge(s[1:], part1[1:], part2)            or s[0] == part2[0] and is_merge(s[1:], part1, part2[1:])

Потребляемую память можно уменьшить, если оперировать индексами (позициями символов), а не целыми строками

Если функцию is_merge закэшировать, то получим рекурсию + динамику.
Это гарантирует максимальное время работы за O(N^2) от длины строки

from functools import lru_cache

@lru_cache()
def is_merge(s, part1, part2):
    if part1 == '':
        return s == part2
    if part2 == '':
        return s == part1
    if s == '':
        return False
    return s[0] == part1[0] and is_merge(s[1:], part1[1:], part2)            or s[0] == part2[0] and is_merge(s[1:], part1, part2[1:])

Потребляемую память можно уменьшить, если оперировать индексами (позициями символов), а не целыми строками