Разбиение палиндрома II
Объедините заранее вычисленную таблицу палиндромов с одномерным DP, чтобы найти минимальное число разрезов для разбиения строки на палиндромы
«Разбиение палиндрома II» — бесплатный урок DSA Interview Prep на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения DSA Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс DSA Interview Prep содержит 4 уроков всего.
Задача: минимальное число разрезов для разбиения
Разбиение на палиндромы II требует для заданной строки s найти минимальное число разрезов, чтобы каждая подстрока в разбиении была палиндромом. Для 'aab' достаточно одного разреза, дающего ['aa', 'b'], поэтому ответ равен 1. Для 'a' ответ равен 0: строка уже является палиндромом. Эта задача объединяет две фазы DP: сначала предварительно вычислить, какие подстроки являются палиндромами, а затем использовать одномерный DP для поиска минимального числа разрезов.
Фаза 1: предварительное вычисление таблицы палиндромов
Сначала постройте is_pal[i][j] = True, если s[i..j] является палиндромом, используя интервальное DP. Это занимает O(n²) времени и O(n²) памяти. В качестве альтернативы расширение вокруг центра заполняет ту же таблицу за O(n²) времени. Эта таблица нужна потому, что одномерный DP разрезов будет многократно обращаться к is_pal[i][j]; предварительное вычисление позволяет не повторять проверки на палиндром внутри цикла DP разрезов.
def build_palindrome_table(s):
n = len(s)
is_pal = [[False]*n for _ in range(n)]
for i in range(n):
is_pal[i][i] = True
for i in range(n-1):
is_pal[i][i+1] = (s[i] == s[i+1])
for length in range(3, n+1):
for i in range(n-length+1):
j = i + length - 1
is_pal[i][j] = (s[i] == s[j]) and is_pal[i+1][j-1]
return is_pal
print(build_palindrome_table('aab'))Фаза 2: настройка одномерного DP разрезов
Определите cuts[i] как минимальное число разрезов для разбиения s[0..i]. Если сама s[0..i] является палиндромом, то cuts[i] = 0. В противном случае переберите все варианты разделения: для каждого j от 0 до i-1, если s[j+1..i] является палиндромом, тогда cuts[i] = min(cuts[i], cuts[j] + 1). Мы задаём вопрос: что, если последним фрагментом разбиения является s[j+1..i]? Тогда для префикса требуется cuts[j] разрезов плюс ещё один разрез.
def min_cut(s):
n = len(s)
is_pal = build_palindrome_table(s)
cuts = [float('inf')] * n
for i in range(n):
if is_pal[0][i]:
cuts[i] = 0 # entire prefix is a palindrome
else:
for j in range(i):
if is_pal[j+1][i]:
cuts[i] = min(cuts[i], cuts[j] + 1)
return cuts[n-1]Полное решение и пошаговый разбор
Проследим решение для 'aab'. Таблица палиндромов: is_pal[0][0]='a'=T, is_pal[1][1]='a'=T, is_pal[2][2]='b'=T, is_pal[0][1]='aa'=T, is_pal[1][2]='ab'=F, is_pal[0][2]='aab'=F. Разрезы: cuts[0]=0 («a» — палиндром), cuts[1]=0 («aa» — палиндром), cuts[2]: «aab» не является палиндромом, поэтому попробуем j=1: is_pal[2][2]=T, следовательно, cuts[2] = cuts[1]+1 = 1. Ответ: 1.
def build_palindrome_table(s):
n = len(s)
is_pal = [[False]*n for _ in range(n)]
for i in range(n):
is_pal[i][i] = True
for i in range(n-1):
is_pal[i][i+1] = (s[i] == s[i+1])
for length in range(3, n+1):
for i in range(n-length+1):
j = i + length - 1
is_pal[i][j] = (s[i] == s[j]) and is_pal[i+1][j-1]
return is_pal
def min_cut(s):
n = len(s)
is_pal = build_palindrome_table(s)
cuts = [float('inf')] * n
for i in range(n):
if is_pal[0][i]:
cuts[i] = 0
else:
for j in range(i):
if is_pal[j+1][i]:
cuts[i] = min(cuts[i], cuts[j] + 1)
return cuts[n-1]
print(min_cut('aab')) # 1
print(min_cut('ababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab'))Сложность по времени и памяти
Фаза 1 (таблица палиндромов) выполняется за O(n²) времени и O(n²) памяти. Фаза 2 (DP разрезов) содержит внешний цикл по n позициям и внутренний цикл по n точкам разделения, поэтому также требует O(n²) времени. Итого: O(n²) времени и O(n²) памяти. Объём памяти для массива разрезов можно сократить до O(n), но таблица палиндромов по-прежнему требует O(n²). На собеседовании ожидается решение за O(n²); решение за O(n) с использованием алгоритма Манакера выходит за рамки типичного материала.
Расширение вокруг центра для таблицы палиндромов
Вместо интервального DP-подхода к построению таблицы палиндромов можно заполнить is_pal с помощью расширения вокруг центра. Для каждой позиции центра расширяйтесь наружу и отмечайте все найденные палиндромы. Это по-прежнему занимает O(n²) времени и O(n²) памяти, но на практике может работать быстрее благодаря более эффективному использованию кэша. На собеседовании допустимы оба подхода.
def build_pal_expand(s):
n = len(s)
is_pal = [[False]*n for _ in range(n)]
def expand(l, r):
while l >= 0 and r < n and s[l] == s[r]:
is_pal[l][r] = True
l -= 1; r += 1
for i in range(n):
expand(i, i) # odd-length centres
expand(i, i+1) # even-length centres
return is_pal
print('Expand-around-centre palindrome table built')Перечисление всех разбиений (часть I)
Разбиение на палиндромы I (связанная задача) требует перечислить ALL допустимых разбиений, в которых каждая подстрока является палиндромом. Для этого используется поиск с возвратом, а предварительно вычисленная таблица палиндромов служит инструментом отсечения. В отличие от DP минимального числа разрезов, который подсчитывает варианты, этот подход перечисляет экспоненциально много решений и полностью решается иным способом.
def partition_all(s):
n = len(s)
is_pal = build_pal_expand(s)
result = []
def backtrack(start, path):
if start == n:
result.append(path[:])
return
for end in range(start, n):
if is_pal[start][end]:
path.append(s[start:end+1])
backtrack(end+1, path)
path.pop()
backtrack(0, [])
return result
print(partition_all('aab')) # [['a','a','b'], ['aa','b']]Инициализация разрезов значением n-1
Распространённый приём: инициализируйте cuts[i] = i вместо inf, поскольку в худшем случае для s[0..i] каждый символ приходится отделять отдельным разрезом, что даёт i разрезов. Благодаря этому в коде не нужно проверять значение inf. Когда is_pal[0][i] равно true, замените значение на 0. Такая инициализация проясняет верхнюю границу числа разрезов и немного упрощает код.
def min_cut_clean(s):
n = len(s)
is_pal = build_palindrome_table(s)
cuts = list(range(n)) # cuts[i] = i (worst case)
for i in range(n):
if is_pal[0][i]:
cuts[i] = 0
else:
for j in range(1, i+1):
if is_pal[j][i]:
cuts[i] = min(cuts[i], cuts[j-1] + 1)
return cuts[n-1]Альтернатива: одномерный DP без отдельной таблицы
Элегантный вариант одновременно заполняет таблицу палиндромов и выполняет DP разрезов. По мере расширения палиндромов от каждого центра сразу обновляйте массив cuts. Для палиндрома s[l..r] можно обновить cuts[r] = min(cuts[r], (cuts[l-1]+1 if l > 0 else 0)). Это устраняет отдельный проход по таблице O(n²) и может упростить реализацию на собеседовании в условиях дефицита времени.
Крайние случаи, которые следует учитывать
Ключевые крайние случаи для разбиения на палиндромы II: (1) строка из одного символа даёт 0 разрезов; (2) строка, уже являющаяся палиндромом, даёт 0 разрезов; (3) строка, состоящая из полностью различных символов, требует n-1 разрезов; (4) строка, состоящая из одинаковых символов (например, 'aaaa'), требует 0 разрезов, поскольку вся строка является палиндромом. Всегда проверяйте, что ваше решение правильно обрабатывает ранний выход при is_pal[0][i] = True.
def build_palindrome_table(s):
n = len(s)
is_pal = [[False]*n for _ in range(n)]
for i in range(n):
is_pal[i][i] = True
for i in range(n-1):
is_pal[i][i+1] = (s[i] == s[i+1])
for length in range(3, n+1):
for i in range(n-length+1):
j = i + length - 1
is_pal[i][j] = (s[i] == s[j]) and is_pal[i+1][j-1]
return is_pal
def min_cut(s):
n = len(s)
is_pal = build_palindrome_table(s)
cuts = list(range(n))
for i in range(n):
if is_pal[0][i]:
cuts[i] = 0
else:
for j in range(1, i+1):
if is_pal[j][i]:
cuts[i] = min(cuts[i], cuts[j-1] + 1)
return cuts[n-1]
print(min_cut('a')) # 0
print(min_cut('aaaa')) # 0
print(min_cut('abc')) # 2Советы по объяснению на собеседовании
Представляя эту задачу на собеседовании, начните с подхода из двух фаз: сначала постройте таблицу палиндромов, затем выполните одномерный DP для массива разрезов. Перед написанием кода объясните рекуррентное соотношение словами. Упомяните, что таблица палиндромов содержит O(n²) элементов и каждый из них заполняется за O(1) с помощью рекуррентного соотношения интервального DP. Перед написанием полного решения всегда пошагово разберите пример, чтобы продемонстрировать корректность в условиях дефицита времени.
Быстрая проверка
Проверьте, насколько вы поняли концепции «Структуры данных и алгоритмы — подготовка к собеседованию по программированию», изученные на этом уроке.
Итоги урока
В этом уроке вы узнали: разбиение на палиндромы II использует две фазы DP — предварительное вычисление таблицы палиндромов, а затем одномерный DP разрезов, рекуррентное соотношение для разрезов имеет вид cuts[i] = min(cuts[j-1] + 1) для всех j, при которых s[j..i] является палиндромом, а общая сложность составляет O(n²) времени и O(n²) памяти. Далее мы рассмотрим задачу о лопающихся шарах, в которой используется cleverный обратный подход к интервальному DP.
Часто задаваемые вопросы
Урок «Разбиение палиндрома II» бесплатный?
Да — полный текст урока «Разбиение палиндрома II» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс DSA Interview Prep, подпишись на CoddyKit PRO. Курс DSA Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Разбиение палиндрома II»?
Объедините заранее вычисленную таблицу палиндромов с одномерным DP, чтобы найти минимальное число разрезов для разбиения строки на палиндромы Ты практикуешь DSA Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать DSA Interview Prep?
Предыдущий опыт не требуется. DSA Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.
Сколько времени занимает урок «Разбиение палиндрома II»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке DSA Interview Prep?
Да. Каждый урок DSA Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Шаблон интервального DP и порядок заполнения
- Наибольшая палиндромная подпоследовательность и подстрока
- Разбиение палиндрома II
- Взрыв шариков: интервальный DP в обратном порядке