Разбиение строки на палиндромы: LeetCode 131 и 132 — бэктрекинг и ДП
Palindrome Partitioning: все разбиения строки на палиндромы бэктрекингом с предподсчётом isPal (LeetCode 131) и минимальное число разрезов за O(n²) динамикой (LeetCode 132). Код на Python и JS.
Коротко
| LeetCode 131: все разбиения | LeetCode 132: минимум разрезов | |
|---|---|---|
| Что вернуть | Список всех разбиений | Одно число |
| Техника | Бэктрекинг + таблица is_pal | ДП по префиксам + таблица is_pal |
| Время | в худшем случае | |
| Память | на таблицу + ответ | , можно |
| Ограничения |
- Обе задачи стоят на одном фундаменте: таблица
is_pal[i][j]— «является лиs[i..j]палиндромом», считается за . - В 131 ответ сам по себе экспоненциальный, поэтому перебор неизбежен. Таблица лишь убирает лишнюю работу внутри перебора.
- В 132 перебирать разбиения нельзя: вариантов. Нужна динамика
cuts[j]— минимум разрезов для префиксаs[0..j]. - Жадность («откусывай самый длинный палиндром с начала») в 132 не работает. Контрпример —
"aaba".
Постановка задач
LeetCode 131. Palindrome Partitioning. Дана строка s. Разбейте её на подстроки так, чтобы каждая подстрока была палиндромом. Верните все возможные разбиения.
Вход: s = "aab"
Выход: [["a","a","b"], ["aa","b"]]
Вход: s = "a"
Выход: [["a"]]
LeetCode 132. Palindrome Partitioning II. Та же строка, но нужно вернуть минимальное число разрезов, после которых все куски — палиндромы.
Вход: s = "aab" → 1 ("aa" | "b")
Вход: s = "a" → 0
Вход: s = "ab" → 1
Разрезов всегда на один меньше, чем кусков. Ответ 132 не превосходит n - 1: разрезать строку на отдельные символы можно всегда, а одна буква — палиндром.
Если нужно найти не разбиение, а самую длинную палиндромную подстроку — это отдельная задача, она разобрана в статье про самую длинную палиндромную подстроку. Проверка одной строки на палиндром — в разборе Valid Palindrome.
Часть 1. Все разбиения (LeetCode 131)
Интуиция
Представьте, что вы ставите разрезы слева направо. Стоя на позиции start, вы выбираете, где закончится очередной кусок: s[start..start], s[start..start+1], … до конца строки. Если кусок — палиндром, кладёте его в текущий путь и рекурсивно разбиваете остаток. Дошли до конца строки — путь стал готовым разбиением.
Это классический бэктрекинг: выбрать → углубиться → откатить выбор. Дерево решений для "aab":
start=0, остаток "aab"
├── "a" (палиндром) → start=1, остаток "ab"
│ ├── "a" (палиндром) → start=2, остаток "b"
│ │ └── "b" → start=3 ✔ ["a","a","b"]
│ └── "ab" ✘
├── "aa" (палиндром) → start=2, остаток "b"
│ └── "b" → start=3 ✔ ["aa","b"]
└── "aab" ✘
Структура та же, что у генерации подмножеств: между соседними символами разрез либо есть, либо нет — вариантов. Мы просто обрезаем ветки, где кусок не палиндром.
Наивное решение
Проверяем каждый кусок напрямую — разворотом строки:
def partition(s: str) -> list[list[str]]: res, path = [], [] def dfs(start: int) -> None: if start == len(s): res.append(path[:]) # копия! path ещё будет меняться return for end in range(start + 1, len(s) + 1): piece = s[start:end] if piece == piece[::-1]: path.append(piece) dfs(end) path.pop() dfs(0) return res print(partition("aab")) # [['a', 'a', 'b'], ['aa', 'b']]
Это решение проходит на LeetCode: при всё маленькое. Но у него есть очевидная неэффективность: одна и та же подстрока проверяется на палиндромность много раз. Кусок s[5..9] будет проверен в каждой ветке, которая дошла до позиции 5, а таких веток может быть до . Каждая проверка стоит .
Предподсчёт is_pal
Заведём таблицу is_pal[i][j] — является ли s[i..j] (включительно) палиндромом. Рекуррентность простая:
Строка — палиндром, если крайние символы равны и середина — тоже палиндром. Условие j - i < 2 закрывает базу: одна буква (i == j) и две одинаковые буквы (j == i + 1) — палиндромы, середины у них нет.
Важен порядок заполнения: is_pal[i][j] зависит от is_pal[i+1][j-1], то есть от строки ниже. Поэтому i идёт с конца, а j — от i вправо:
def build_is_pal(s: str) -> list[list[bool]]: n = len(s) is_pal = [[False] * n for _ in range(n)] for i in range(n - 1, -1, -1): for j in range(i, n): if s[i] == s[j] and (j - i < 2 or is_pal[i + 1][j - 1]): is_pal[i][j] = True return is_pal
Это стандартный приём интервальной динамики: ответ для отрезка строится из ответа для отрезка покороче. Для "aab" таблица выглядит так (T — палиндром, · — нет, под диагональю ячейки не используются):
j=0 j=1 j=2
i=0 T T · "a" "aa" "aab"
i=1 T · "a" "ab"
i=2 T "b"
Таблицу можно строить и иначе — расширением от центров, как в задаче о самой длинной палиндромной подстроке. Результат тот же, асимптотика тоже .
Оптимальное решение
Теперь проверка куска — обращение к таблице за :
def partition(s: str) -> list[list[str]]: n = len(s) is_pal = build_is_pal(s) res, path = [], [] def dfs(start: int) -> None: if start == n: res.append(path[:]) return for end in range(start, n): # end — включительно if is_pal[start][end]: path.append(s[start:end + 1]) dfs(end + 1) path.pop() dfs(0) return res print(partition("aab")) # [['a', 'a', 'b'], ['aa', 'b']] print(len(partition("aaaa"))) # 8
Обратите внимание на смену индексов: в наивной версии end был границей среза (не включительно), здесь — индексом последнего символа куска. Путаница между этими двумя соглашениями — главный источник ошибок на ±1 в этой задаче.
То же на JavaScript:
function partition(s) { const n = s.length const isPal = Array.from({ length: n }, () => new Array(n).fill(false)) for (let i = n - 1; i >= 0; i--) for (let j = i; j < n; j++) isPal[i][j] = s[i] === s[j] && (j - i < 2 || isPal[i + 1][j - 1]) const res = [] const path = [] const dfs = (start) => { if (start === n) { res.push([...path]) return } for (let end = start; end < n; end++) { if (!isPal[start][end]) continue path.push(s.slice(start, end + 1)) dfs(end + 1) path.pop() } } dfs(0) return res } console.log(JSON.stringify(partition('aab'))) // [["a","a","b"],["aa","b"]]
Сложность 131
Худший случай — строка из одинаковых букв, например "aaaa". Тогда любая подстрока — палиндром, и любое из разбиений подходит:
| n | 1 | 2 | 3 | 4 | 5 | 10 | 16 |
|---|---|---|---|---|---|---|---|
разбиений "a"*n | 1 | 2 | 4 | 8 | 16 | 512 | 32 768 |
Каждое разбиение копируется в ответ за , отсюда по времени. Предподсчёт на этом фоне незаметен. Память: на таблицу, на стек рекурсии и путь, плюс сам ответ — символов.
Честно скажем: на тестах LeetCode наивная и оптимальная версии работают почти одинаково быстро, потому что строки короткие. Таблица is_pal ценна не столько ускорением, сколько тем, что это та же таблица, которая понадобится во второй задаче. На собеседовании её построение показывает, что вы видите повторяющиеся подзадачи. Именно этого обычно ждут в follow-up.
Можно пойти дальше и мемоизировать не только проверку, но и сами списки разбиений для каждого суффикса (dfs(start) возвращает все разбиения s[start:]). Асимптотику ответа это не улучшит: его размер всё равно экспоненциальный.
Часть 2. Минимальное число разрезов (LeetCode 132)
Почему перебор не подходит
Ответ 132 равен «минимальная длина разбиения минус один». Можно было бы взять решение 131 и найти самый короткий список. Но при и строке "aaa…a" разбиений . Даже с отсечениями перебор не уложится ни в какие лимиты.
Нужна динамика. Заметим: оптимальное разбиение префикса заканчивается каким-то палиндромом s[i..j]. Всё, что левее, — тоже оптимально разбитый префикс s[0..i-1]. Это и есть оптимальная подструктура.
Неправильная жадность
Первая мысль многих — откусывать самый длинный палиндром с начала строки. Проверим на "aaba":
- жадно:
"aa" | "b" | "a"— 2 разреза; - оптимально:
"a" | "aba"— 1 разрез.
Взяв длинный "aa", жадность «съела» букву, которая была нужна для "aba". Локально лучший выбор не ведёт к глобальному оптимуму. Такие ловушки подробно разобраны в статье про жадные алгоритмы.
Состояние и переход
cuts[j] — минимальное число разрезов для префикса s[0..j] (включительно).
Переход: перебираем начало i последнего куска.
- Если
s[0..j]целиком палиндром, тоcuts[j] = 0. - Иначе для каждого
iот 1 доj, гдеs[i..j]— палиндром:cuts[j] = min(cuts[j], cuts[i-1] + 1).
Минимум всегда существует: при i = j кусок — одна буква, а это палиндром. Ответ — cuts[n-1].
def min_cut(s: str) -> int: n = len(s) is_pal = build_is_pal(s) cuts = [0] * n for j in range(n): if is_pal[0][j]: cuts[j] = 0 continue best = j # верхняя оценка: режем на отдельные буквы for i in range(1, j + 1): if is_pal[i][j]: best = min(best, cuts[i - 1] + 1) cuts[j] = best return cuts[-1] print(min_cut("aab")) # 1 print(min_cut("aaba")) # 1 print(min_cut("abacdc")) # 1: "aba" | "cdc"
Разбор на примере "aaba"
Таблица палиндромов для "aaba": палиндромы — все одиночные буквы, "aa" (0..1) и "aba" (1..3).
| j | префикс | is_pal[0][j] | кандидаты i | cuts[j] |
|---|---|---|---|---|
| 0 | a | да | — | 0 |
| 1 | aa | да | — | 0 |
| 2 | aab | нет | i=2 ("b"): cuts[1]+1 = 1 | 1 |
| 3 | aaba | нет | i=1 ("aba"): cuts[0]+1 = 1; i=3 ("a"): cuts[2]+1 = 2 | 1 |
На шаге j = 3 динамика «вспомнила» вариант с коротким первым куском "a", который жадность выбросила.
Сложность 132
Таблица is_pal — по времени и памяти. Двойной цикл по j и i — ещё . Итого : при это около 4 млн операций.
В Python таблица 2000 × 2000 из булевых значений — это 4 млн ссылок в списках, порядка 32 МБ. Это проходит, но есть вариант экономнее.
Оптимизация памяти: расширение от центров
Таблицу можно не хранить. Будем перебирать центры палиндромов и расширяться в обе стороны. Каждый найденный палиндром s[lo..hi] сразу обновляет ответ для префикса, который он завершает.
Удобно сдвинуть индексацию: cuts[k] — минимум разрезов для префикса длины k, а cuts[0] = -1. Тогда палиндром s[lo..hi] даёт кандидата cuts[lo] + 1 для cuts[hi + 1], и случай «весь префикс — палиндром» (lo = 0) обрабатывается автоматически: -1 + 1 = 0.
def min_cut(s: str) -> int: n = len(s) cuts = list(range(-1, n)) # cuts[k] = k - 1: режем на отдельные буквы for center in range(n): # нечётные палиндромы (center, center) и чётные (center, center + 1) for lo, hi in ((center, center), (center, center + 1)): while lo >= 0 and hi < n and s[lo] == s[hi]: cuts[hi + 1] = min(cuts[hi + 1], cuts[lo] + 1) lo -= 1 hi += 1 return cuts[n] print(min_cut("aab")) # 1 print(min_cut("aaba")) # 1
Почему порядок обхода корректен? Когда мы обновляем cuts[hi + 1] через cuts[lo], значение cuts[lo] уже окончательное. Все палиндромы, которые заканчиваются на позиции lo - 1, имеют центр не правее lo - 1. Значит, их обработали на предыдущих итерациях внешнего цикла. Время по-прежнему , память — .
Версия на JavaScript с таблицей, которая заполняется прямо по ходу (столбец j нужен только для текущей итерации и опирается на столбец j - 1, посчитанный раньше):
function minCut(s) { const n = s.length const isPal = Array.from({ length: n }, () => new Array(n).fill(false)) const cuts = new Array(n).fill(0) for (let j = 0; j < n; j++) { let best = j for (let i = 0; i <= j; i++) { if (s[i] === s[j] && (j - i < 2 || isPal[i + 1][j - 1])) { isPal[i][j] = true best = i === 0 ? 0 : Math.min(best, cuts[i - 1] + 1) } } cuts[j] = best } return cuts[n - 1] } console.log(minCut('aab'), minCut('a'), minCut('ab')) // 1 0 1
Здесь i === 0 проверяется первым по ходу цикла. Если весь префикс — палиндром, best сразу становится 0, и дальше Math.min уже ничего не уменьшит.
Существует и линейное решение на основе алгоритма Манакера или палиндромического дерева. На собеседованиях его почти никогда не ждут: — это целевой ответ.
Типичные ошибки
- Не копируют путь.
res.append(path)вместоres.append(path[:])— в ответе окажется много ссылок на один и тот же список, который к концу перебора станет пустым. В JS — то же самое сres.push(path). - Неправильный порядок заполнения
is_pal. Еслиiидёт от 0 вверх, тоis_pal[i+1][j-1]к моменту обращения ещё не посчитан. Внешний цикл поi— с конца, либо внешний поj— с начала. - Путают границы. Срез
s[start:end]не включаетend, аis_pal[start][end]— включает. Выберите одно соглашение и держитесь его во всём коде. - Забывают базу
j - i < 2. Без неё"aa"обратится кis_pal[1][0]— ячейке под диагональю, где лежитFalse. Двухбуквенные палиндромы потеряются. - Решают 132 жадно или перебором из 131. Жадность ломается на
"aaba", перебор — на длинной строке из одинаковых букв. - Путают разрезы и куски. Число разрезов — на единицу меньше числа кусков. Если
dpсчитает куски, не забудьте вычесть 1, иначе"a"даст 1 вместо 0. - Проверяют палиндромность внутри двойного цикла в 132 срезом.
s[i:j+1] == s[i:j+1][::-1]превращает в . При это уже 8 млрд операций в худшем случае.
Где встречается на собеседованиях
Palindrome Partitioning — входит в раздел «Backtracking» популярного списка NeetCode 150. Типичный сценарий на интервью:
- Сначала просят 131. Ожидают бэктрекинг с шаблоном
choose → explore → unchoose, аккуратную работу с копией пути и оценку сложности с объяснением, откуда она берётся. - Follow-up: «проверка палиндрома повторяется — можно ли быстрее?» Здесь нужна таблица
is_pal. - Второй follow-up: «а если нужно только минимальное число разрезов?» Это 132. Хороший ответ: сначала объяснить, почему перебор и жадность не годятся, затем сформулировать состояние
cuts[j]и переход.
Близкие задачи, которые решаются тем же мышлением:
- Word Break — та же схема «последний кусок + оптимальный префикс», только кусок должен быть словом из словаря, а не палиндромом. Word Break II — аналог 131 с перечислением всех разбиений.
- Combination Sum и перестановки — тот же каркас бэктрекинга.
- Decode Ways — ДП по префиксам с переходами на 1–2 символа назад.
- Интервальная динамика — порядок заполнения таблицы по отрезкам, как в
is_pal.
Итог
is_pal[i][j]за — общая основа обеих задач. Заполняйтеiс конца.- 131: бэктрекинг по позиции начала следующего куска, проверка через таблицу, копия пути при записи в ответ. Время — столько стоит сам ответ.
- 132:
cuts[j] = min(cuts[i-1] + 1)по всем палиндромамs[i..j], база — весь префикс палиндром. Время , память или с расширением от центров. - Жадность не работает:
"aaba"— ваш контрпример на собеседовании.