Задача с собеседования в Amazon

Дана строка s. Разбить s так, чтобы каждая подстрока разбиения была палиндромом. Вернуть все возможные разбиения строки на палиндромы.

Пример:
Input: s = "aab"
Output: [["a","a","b"], ["aa","b"]]

|s| <= 16

Наш чат алгоритмистов

Решение:

Самое простое решение
Используем рекурсивный возврат с откатом:
1. На каждом шаге пробуем все возможные подстроки, начиная с текущей позиции
2. Если подстрока является палиндромом — добавляем её в текущий путь и рекурсивно продолжаем с оставшейся частью строки
3. Когда достигаем конца строки — сохраняем текущее разбиение
4. Откатываемся и пробуем другие варианты

Это даёт O(n × 2^n) по времени (2^(n-1) возможных разбиений, для каждого O(n) на проверку) и O(n) по памяти для стека рекурсии.

def partition(s: str) -> List[List[str]]:
def is_palindrome(string: str) -> bool:
return string == string[::-1]

def backtrack(start: int, path: List[str]) -> None:
if start == len(s):
result.append(path[:])
return

for end in range(start + 1, len(s) + 1):
substring = s[start:end]
if is_palindrome(substring):
path.append(substring)
backtrack(end, path)
path.pop()

result = []
backtrack(0, [])
return result

Оптимизация:
Можно предварительно вычислить все палиндромы с помощью DP за O(n²), чтобы потом проверять их за O(1). Но для |s| <= 16 рекурсии достаточно

@algoses