Palindrome Partitioning

Q: Jaka jest złożoność czasowa problemu podziału na palindromy?

W ciągu jednakowych liter wszystkie 2^(n-1) podziały są odpowiedziami, każda o długości do 2n-1 znaków: O(n × 2^n) . Żadna metoda nie jest od tego szybsza, ponieważ zapisanie odpowiedzi wymaga tyle samo pracy. Tablica palindromów wymaga O(n²) czasu i miejsca, a rekurencja O(n) .

Q: Ile podziałów na palindromy może mieć ciąg znaków?

Co najwyżej 2^(n-1) , po jednym dla każdego sposobu wyboru, które z n-1 przerw przeciąć. Ciąg jednakowych liter osiąga tę granicę: 1,024 podziałów dla 11 liter. Ciąg bez powtarzających się liter ma dokładnie jeden podział — każda litera osobno.

Q: Czy podział palindromu to programowanie dynamiczne czy wycofywanie?

Wykorzystuje oba podejścia. Wypisanie wszystkich podziałów, których liczba może wynieść do 2^(n-1) , wymaga wyszukiwania, które buduje każdy podział kawałek po kawałku: nawrotów. Programowanie dynamiczne dostarcza tabelę z odpowiedziami tak lub nie dla podciągów będących palindromami, z której korzysta wyszukiwanie; tabela jest wypełniana raz w czasie O(n²) .

ŚrednieNawroty Programowanie dynamiczne

+10

Palindrom czyta się tak samo od lewej do prawej i od prawej do lewej. Podziel ciąg znaków s na co najmniej jedną część tak, aby każda część była palindromem, i zwróć wszystkie możliwe podziały.

Zapisz każdy podział jako jego części w kolejności, połączone znakiem |: podział aab na a, a i b daje a|a|b. Zwróć podziały posortowane rosnąco według kodów znaków, tak aby | znajdował się po każdej małej literze.

Funkcja

partition(s: string) → string-array

sstring: ciąg małych liter do wycięcia
Zwracastring-array: każdy podział s na palindromy, zapisany z | między częściami, w kolejności rosnącej

Ograniczenia

1 ≤ s.length ≤ 11
s zawiera wyłącznie małe litery alfabetu angielskiego.
Ciąg 11 jednakowych liter ma 1,024 podziałów — to największa odpowiedź.

Przykłady

Wejście: s = "aab"
Wyjście: ["aa|b", "a|a|b"]
Wyjaśnienie: Tylko aa|b i a|a|b mają wyłącznie palindromiczne części; a|ab nie przechodzi dla ab. aa|b sortuje się jako pierwsze: na drugim znaku ma a, podczas gdy drugi ciąg ma |, który sortuje się po każdej literze.

Wejście: s = "abba"
Wyjście: ["abba", "a|bb|a", "a|b|b|a"]
Wyjaśnienie: abba samo w sobie jest palindromem, więc ciąg bez cięć jest podziałem i sortuje się jako pierwszy: jego drugi znak to litera. a|bb|a występuje przed a|b|b|a: na czwartym znaku ma b, podczas gdy drugi ciąg ma |.

Pytanie dodatkowe

Czy potrafisz znaleźć najmniejszą liczbę cięć, która dzieli s na palindromy, dla ciągów o długości do 2 000?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Każda z n-1 przerw między literami jest albo rozcinana, albo nie, więc istnieje 2^(n-1) podziałów i każdy z nich może być odpowiedzią. Nie da się zmniejszyć rozmiaru wyniku, ale można pomijać podziały, które nie spełniają warunku: buduj każdy podział od lewej do prawej, odcinaj tylko fragmenty będące palindromami i odczytuj palindromy z tabeli wypełnionej tylko raz.

Wypróbuj każdy zestaw cięć

Intuicja

Ponumeruj podziały liczbami całkowitymi od 0 do 2^(n-1)-1, przy czym każdy bit wskazuje, czy przecięto jedną przerwę. Zachowaj podział danej liczby, jeśli każdy fragment jest palindromem.

Jeśli pierwszej przerwie odpowiada najwyższy bit, liczenie w górę wylicza podziały w kolejności rosnącej. Dla dwóch liczb najwyższy bit, którym się różnią, odpowiada najwcześniejszej przerwie, którą jedna z nich przecina, a druga nie. Wcześniej ciągi są równe; w tym miejscu mniejsza liczba ma literę, a większa ma |, który sortuje się po każdej literze. Dla aab, 1 daje aa|b, a 3 daje a|a|b.

Dla 11 liter daje to 1,024 masek, każda po 11 liter. Marnotrawstwo wynika z odrzucanych podziałów: abcdefghijk tworzy wszystkie 1,024, aby znaleźć jedną odpowiedź.

Algorytm

Iteruj po mask od 0 do 2^(n-1)-1.
Przejdź po literach; zakończ część po literze i, gdy i jest ostatnim indeksem lub bit n-2-i w mask jest ustawiony.
Sprawdź każdą część, przesuwając dwa wskaźniki do środka.
Jeśli każda część jest palindromem, połącz części za pomocą | i dodaj ciąg do odpowiedzi.
Zwróć odpowiedź; jest już posortowana, ponieważ pierwsza przerwa odpowiada najwyższemu bitowi.

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

Wycofywanie z użyciem tablicy palindromów

Intuicja

Pierwszy fragment jest palindromicznym prefiksem s[0..end], a podział pozostałej części to ten sam problem zaczynający się od end+1. Dlatego backtrack(start) wypróbowuje każdą wartość end, dla której s[start..end] jest palindromem, dodaje fragment, wykonuje rekurencję i usuwa go. Każda gałąź kończy się odpowiedzią, ponieważ pojedyncza litera jest palindromem, więc nakład pracy zależy od rozmiaru wyniku: dla abcdefghijk wyszukiwanie przechodzi jedną ścieżkę.

To, czy s[start..end] jest palindromem, sprawdza się w wielu gałęziach, więc odczytuj tę informację z tabeli: s[i..j] ma wartość jeden, gdy s[i] == s[j] i wnętrze s[i+1..j-1] ma wartość jeden, albo gdy fragment ma co najwyżej 2 litery.

Wypróbowywanie wartości end od ostatniego indeksu w dół daje posortowany wynik. Dwa podziały z różnymi pierwszymi fragmentami są zgodne aż do końca krótszego fragmentu; w tym miejscu krótszy ma |, a dłuższy ma literę, więc dłuższy pierwszy fragment sortuje się wcześniej.

Algorytm

Wypełnij pal[i][j] dla i od n-1 w dół do 0: s[i] == s[j] oraz albo j-i < 2, albo pal[i+1][j-1].
Napisz backtrack(start). Jeśli start jest równe n, połącz bieżące części za pomocą | i zapisz ciąg.
W przeciwnym razie wykonuj pętlę po end od n-1 w dół do start i pomiń tę wartość, jeśli pal[start][end] nie jest prawdą.
Dodaj s[start..end] do części, wywołaj backtrack(end+1), a następnie usuń tę część.
Wywołaj backtrack(0) i zwróć zapisane podziały, już posortowane.

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

Pułapki i przypadki brzegowe

Próbowanie najkrótszego fragmentu jako pierwszego. Podziały są poprawne, ale ich kolejność jest błędna: a|a|b przed aa|b.
Sortowanie na końcu za pomocą porównania uwzględniającego reguły języka lub ustawień regionalnych, które może umieścić | przed literami. Porównuj kody znaków albo generuj podziały w odpowiedniej kolejności.
Wypełnianie tablicy palindromów przy rosnącym i. Wtedy pal[i+1][j-1] jest odczytywane, zanim zostanie obliczone; wypełniaj tablicę dla i od n-1 w dół.
Łączenie włącznie końcowego end z wyłącznym końcem podciągu. Fragment s[start..end] ma end-start+1 liter.
Zapisywanie współdzielonej listy fragmentów zamiast połączonego ciągu znaków. Wyszukiwanie ciągle zmienia tę listę, więc każdy zapisany wpis okazuje się taki sam.

Najczęstsze pytania3

Jaka jest złożoność czasowa problemu podziału na palindromy?

W ciągu jednakowych liter wszystkie 2^(n-1) podziały są odpowiedziami, każda o długości do 2n-1 znaków: O(n × 2^n). Żadna metoda nie jest od tego szybsza, ponieważ zapisanie odpowiedzi wymaga tyle samo pracy. Tablica palindromów wymaga O(n²) czasu i miejsca, a rekurencja O(n).

Ile podziałów na palindromy może mieć ciąg znaków?

Co najwyżej 2^(n-1), po jednym dla każdego sposobu wyboru, które z n-1 przerw przeciąć. Ciąg jednakowych liter osiąga tę granicę: 1,024 podziałów dla 11 liter. Ciąg bez powtarzających się liter ma dokładnie jeden podział — każda litera osobno.

Czy podział palindromu to programowanie dynamiczne czy wycofywanie?

Wykorzystuje oba podejścia. Wypisanie wszystkich podziałów, których liczba może wynieść do 2^(n-1), wymaga wyszukiwania, które buduje każdy podział kawałek po kawałku: nawrotów. Programowanie dynamiczne dostarcza tabelę z odpowiedziami tak lub nie dla podciągów będących palindromami, z której korzysta wyszukiwanie; tabela jest wypełniana raz w czasie O(n²).

def partition(s):
    # Napisz kod tutaj

Test #1

Test #2

Argument

s = "aab"

Oczekiwany wynik

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