Если функцию 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:])

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

ДОБАВЛЕНО:
Вообще, т.к. в кэш передаются полные строки (длины N), то полная сложность здесь будет O(N^3)
Но если работать с индексами, то получим обозначенные O(N^2)