Palindrome Partitioning

Q: Какова временная сложность разбиения строки на палиндромы?

Для строки из одинаковых букв все 2^(n-1) разбиений являются ответами, каждое длиной до 2n-1 символов: O(n × 2^n) . Ни один метод не может быть эффективнее, поскольку запись ответа требует столько же ресурсов. Таблица палиндромов добавляет O(n²) времени и памяти, а рекурсия — O(n) .

Q: Сколько разбиений на палиндромы может иметь строка?

Не более 2^(n-1) — по одному для каждого способа выбрать, какие из n-1 промежутков разрезать. Строка из одинаковых букв достигает этой границы: 1 024 разбиения для 11 букв. Строка без повторяющихся букв имеет ровно одно разбиение — каждая буква отдельно.

Q: Разбиение палиндрома — это динамическое программирование или алгоритм с возвратом?

Здесь используются оба подхода. Перечисление всех разбиений вплоть до 2^(n-1) требует поиска, который строит каждое разбиение по частям: поиска с возвратом. Динамическое программирование заполняет за O(n²) таблицу с ответами «да» или «нет» для палиндромных подстрок, которую использует поиск.

СреднеПоиск с возвратом Динамическое программирование

+10

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

Записывайте каждое разбиение как последовательность частей, соединённых символом |: разбиение aab на a, a и b даёт a|a|b. Верните разбиения, отсортированные по возрастанию кодов символов, так что | идёт после всех строчных букв.

Функция

partition(s: string) → string-array

sstring: строка строчных букв, которую нужно вырезать
Возвращаетstring-array: каждое разбиение s на палиндромы, записанное с помощью | между частями, в порядке возрастания

Ограничения

1 ≤ s.length ≤ 11
s содержит только строчные буквы английского алфавита.
Строка из 11 одинаковых букв имеет 1,024 варианта разбиения — это наибольший ответ.

Примеры

Ввод: s = "aab"
Вывод: ["aa|b", "a|a|b"]
Пояснение: Только aa|b и a|a|b состоят из палиндромных частей; вариант a|ab не подходит из-за ab. Первым при сортировке идёт aa|b: во втором символе у него стоит a, тогда как у другого — |, который сортируется после любой буквы.

Ввод: s = "abba"
Вывод: ["abba", "a|bb|a", "a|b|b|a"]
Пояснение: abba — это палиндром, поэтому неразрезанная строка является разбиением и сортируется первой: её второй символ — буква. a|bb|a идёт перед a|b|b|a: на четвёртой позиции у неё b, тогда как у другой — |.

Дополнительный вопрос

Сможешь найти наименьшее число разрезов, которое разделит s на палиндромы для строк длиной до 2 000?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Каждый из n-1 промежутков между буквами либо разрезается, либо нет, поэтому существует 2^(n-1) разбиений, и каждое из них может быть ответом. Невозможно уменьшить размер вывода, но можно пропустить неподходящие разбиения: стройте каждое разбиение слева направо, отделяйте только палиндромные части и определяйте палиндромы по таблице, заполненной заранее.

Попробуйте каждый вариант разрезов

Идея

Пронумеруй разбиения целыми числами от 0 до 2^(n-1)-1, где каждый бит показывает, разрезан ли один из промежутков. Оставляй разбиение с этим номером, если каждая часть является палиндромом.

Если первому промежутку соответствует старший бит, то при подсчёте по возрастанию разбиения перечисляются в возрастающем порядке. Для двух чисел старший бит, в котором они различаются, соответствует самому раннему промежутку, который одно число разрезает, а другое — нет. До него строки равны; в этом месте у меньшего числа стоит буква, а у большего — |, который сортируется после любой буквы. Для aab число 1 даёт aa|b, а число 3 — a|a|b.

Для 11 букв это 1 024 маски, по 11 букв в каждой. Потери возникают из-за неподходящих разбиений: для abcdefghijk строятся все 1 024, чтобы найти один ответ.

Алгоритм

Перебирай значения mask от 0 до 2^(n-1)-1.
Проходи по буквам; заканчивай фрагмент после буквы i, если i — последний индекс или бит n-2-i в mask установлен.
Проверяй каждый фрагмент двумя указателями, движущимися навстречу друг другу.
Если каждый фрагмент является палиндромом, соединяй фрагменты с помощью | и добавляй строку в ответ.
Возвращай ответ; он уже отсортирован, потому что первый разделитель соответствует старшему биту.

def partition(s):
    n = len(s)
    result = []
    # Bit (n-2-i) of mask says whether to cut after s[i]. Counting the
    # masks up from 0 lists the splits in sorted order.
    for mask in range(1 << (n - 1)):
        pieces = []
        start = 0
        for i in range(n):
            if i == n - 1 or (mask >> (n - 2 - i)) & 1:
                pieces.append(s[start:i + 1])
                start = i + 1
        if all(piece == piece[::-1] for piece in pieces):
            result.append("|".join(pieces))
    return result

Поиск с возвратом с использованием таблицы палиндромов

Идея

Первая часть — это палиндромный префикс s[0..end], а разбить оставшуюся часть — та же задача, начиная с end+1. Поэтому backtrack(start) пробует все значения end, при которых s[start..end] является палиндромом, добавляет часть, вызывает рекурсию и удаляет её. Каждая ветвь завершается ответом, поскольку одна буква — это палиндром, поэтому объём работы зависит от размера вывода: для abcdefghijk поиск проходит по одному пути.

Проверка того, является ли s[start..end] палиндромом, выполняется во многих ветвях, поэтому будем получать результат из таблицы: s[i..j] равно единице, если s[i] == s[j] и внутренняя часть s[i+1..j-1] равна единице, либо если в части не более 2 букв.

Перебор end от последнего индекса к первому даёт отсортированный вывод. Два разбиения с разными первыми частями совпадают до конца более короткой части; там у более короткой части стоит |, а у более длинной — буква, поэтому более длинная первая часть сортируется раньше.

Алгоритм

Заполни pal[i][j] для i от n-1 до 0: s[i] == s[j] и либо j-i < 2, либо pal[i+1][j-1].
Напиши backtrack(start). Если start равен n, объедини текущие части с помощью | и сохрани строку.
Иначе перебирай end от n-1 до start и пропускай его, если pal[start][end] не выполняется.
Добавь s[start..end] к частям, вызови backtrack(end+1), затем удали эту часть.
Вызови backtrack(0) и верни сохранённые разбиения, уже отсортированные.

def partition(s):
    n = len(s)
    # pal[i][j] is True when s[i..j] reads the same both ways.
    pal = [[False] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            pal[i][j] = s[i] == s[j] and (j - i < 2 or pal[i + 1][j - 1])
    result = []
    parts = []

    def backtrack(start):
        if start == n:
            result.append("|".join(parts))
            return
        # Longest piece first: "|" sorts after every letter, so a longer
        # first piece gives a smaller string and the output stays sorted.
        for end in range(n - 1, start - 1, -1):
            if pal[start][end]:
                parts.append(s[start:end + 1])
                backtrack(end + 1)
                parts.pop()

    backtrack(0)
    return result

Ловушки и крайние случаи

Сначала пробовать самый короткий фрагмент. Разбиение правильное, но порядок неверный: a|a|b идёт перед aa|b.
Сортировать в конце с помощью сравнения, учитывающего языковые правила или правила локали: из-за этого | может оказаться перед буквами. Сравнивайте коды символов или генерируйте разбиения в нужном порядке.
Заполнять таблицу палиндромов, увеличивая i. В этом случае значение pal[i+1][j-1] считывается до вычисления; заполняйте таблицу, уменьшая i от n-1.
Смешивать включительный end с исключительной конечной позицией подстроки. Фрагмент s[start..end] содержит end-start+1 букв.
Сохранять общий список фрагментов вместо объединённой строки. Поиск продолжает изменять этот список, поэтому все сохранённые записи в итоге становятся одинаковыми.

Частые вопросы3

Какова временная сложность разбиения строки на палиндромы?

Для строки из одинаковых букв все 2^(n-1) разбиений являются ответами, каждое длиной до 2n-1 символов: O(n × 2^n). Ни один метод не может быть эффективнее, поскольку запись ответа требует столько же ресурсов. Таблица палиндромов добавляет O(n²) времени и памяти, а рекурсия — O(n).

Сколько разбиений на палиндромы может иметь строка?

Не более 2^(n-1) — по одному для каждого способа выбрать, какие из n-1 промежутков разрезать. Строка из одинаковых букв достигает этой границы: 1 024 разбиения для 11 букв. Строка без повторяющихся букв имеет ровно одно разбиение — каждая буква отдельно.

Разбиение палиндрома — это динамическое программирование или алгоритм с возвратом?

Здесь используются оба подхода. Перечисление всех разбиений вплоть до 2^(n-1) требует поиска, который строит каждое разбиение по частям: поиска с возвратом. Динамическое программирование заполняет за O(n²) таблицу с ответами «да» или «нет» для палиндромных подстрок, которую использует поиск.

def partition(s):
    # Напишите код здесь

Тест #1

Тест #2

Аргумент

s = "aab"

Ожидаемый вывод

["aa|b", "a|a|b"]