Palindrome Partitioning

Q: Wie hoch ist die Zeitkomplexität der Palindrompartitionierung?

Bei einer Zeichenfolge aus gleichen Buchstaben sind alle 2^(n-1) Aufteilungen Lösungen, jede bis zu 2n-1 Zeichen lang: O(n × 2^n) . Keine Methode ist schneller, da das Ausgeben der Lösung ebenso viel kostet. Die Palindromtabelle benötigt O(n²) Zeit und Speicherplatz, die Rekursion O(n) .

Q: Wie viele Palindromzerlegungen kann ein String haben?

Höchstens 2^(n-1) , eine für jede Möglichkeit, auszuwählen, welche der n-1 Lücken geschnitten werden. Eine Zeichenkette aus gleichen Buchstaben erreicht diese Grenze: 1,024 Aufteilungen bei 11 Buchstaben. Eine Zeichenkette ohne wiederholte Buchstaben hat genau eine Aufteilung, bei der jeder Buchstabe für sich steht.

Q: Ist Palindrome Partitioning dynamische Programmierung oder Backtracking?

Es verwendet beides. Das Auflisten von bis zu 2^(n-1) Aufteilungen erfordert eine Suche, die jede Aufteilung Stück für Stück aufbaut: Backtracking. Die dynamische Programmierung liefert die Ja-Nein-Tabelle der palindromischen Teilzeichenfolgen, die die Suche ausliest und die einmal in O(n²) ausgefüllt wird.

MittelBacktracking Dynamische Programmierung

+10

Ein Palindrom liest sich von links nach rechts und von rechts nach links gleich. Teile die Zeichenfolge s in ein oder mehrere Stücke, sodass jedes Stück ein Palindrom ist, und gib alle Möglichkeiten dafür zurück.

Schreibe jede Aufteilung als ihre Stücke in der richtigen Reihenfolge, getrennt durch |: Wenn aab in a, a und b aufgeteilt wird, ergibt das a|a|b. Gib die Aufteilungen in aufsteigender Reihenfolge zurück, verglichen anhand der Zeichencodes, sodass | nach jedem Kleinbuchstaben kommt.

Funktion

partition(s: string) → string-array

sstring: die Zeichenfolge aus Kleinbuchstaben, die abgeschnitten werden soll
Gibt zurückstring-array: jede Zerlegung von s in Palindrome, mit | zwischen den Teilen, in aufsteigender Reihenfolge

Einschränkungen

1 ≤ s.length ≤ 11
s enthält nur englische Kleinbuchstaben.
Eine Zeichenfolge aus 11 gleichen Buchstaben hat 1,024 Aufteilungen, die größte Antwort.

Beispiele

Eingabe: s = "aab"
Ausgabe: ["aa|b", "a|a|b"]
Erklärung: Nur aa|b und a|a|b bestehen ausschließlich aus palindromischen Teilen; a|ab scheitert an ab. aa|b steht in der Sortierung an erster Stelle: Beim zweiten Zeichen hat es ein a, während das andere ein | hat, das nach jedem Buchstaben sortiert wird.

Eingabe: s = "abba"
Ausgabe: ["abba", "a|bb|a", "a|b|b|a"]
Erklärung: abba ist selbst ein Palindrom, daher ist die ungeteilte Zeichenfolge eine Aufteilung und wird zuerst sortiert: Ihr zweites Zeichen ist ein Buchstabe. a|bb|a kommt vor a|b|b|a: An der vierten Stelle hat sie b, während die andere | hat.

Weiterführende Frage

Kannst du die kleinste Anzahl an Schnitten finden, die s in Palindrome zerlegt, für Zeichenfolgen mit einer Länge von bis zu 2.000?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Jede der n-1 Lücken zwischen den Buchstaben wird entweder getrennt oder nicht, daher gibt es 2^(n-1) Aufteilungen, und jede davon kann eine Antwort sein. Die Größe der Ausgabe lässt sich nicht unterbieten, aber du kannst Aufteilungen überspringen, die nicht funktionieren: Erzeuge jede Aufteilung von links nach rechts, trenne nur palindromische Teilstücke ab und lies die Palindrome aus einer einmalig gefüllten Tabelle ab.

Probiere jede Menge von Schnitten

Idee

Nummeriere die Aufteilungen mit den ganzen Zahlen von 0 bis 2^(n-1)-1; jedes Bit gibt an, ob eine Lücke durchtrennt wird. Behalte die Aufteilung einer Zahl bei, wenn jedes Teilstück ein Palindrom ist.

Wenn die erste Lücke dem höchsten Bit entspricht, listet das Hochzählen die Aufteilungen in aufsteigender Reihenfolge auf. Bei zwei Zahlen ist das höchste Bit, in dem sie sich unterscheiden, die früheste Lücke, die bei der einen durchtrennt wird und bei der anderen nicht. Davor sind die Zeichenfolgen gleich; an dieser Stelle hat die kleinere Zahl einen Buchstaben und die größere |, das nach jedem Buchstaben sortiert wird. Für aab ergibt 1 aa|b und 3 a|a|b.

Bei 11 Buchstaben sind das 1.024 Masken mit jeweils 11 Buchstaben. Die Verschwendung entsteht durch verworfene Aufteilungen: abcdefghijk erzeugt alle 1.024, um eine Antwort zu finden.

Algorithmus

Durchlaufe mask von 0 bis 2^(n-1)-1.
Gehe die Buchstaben durch; beende ein Teilstück nach dem Buchstaben i, wenn i der letzte Index ist oder das Bit n-2-i von mask gesetzt ist.
Prüfe jedes Teilstück mit zwei Zeigern, die sich nach innen bewegen.
Wenn jedes Teilstück ein Palindrom ist, verbinde die Teilstücke mit | und füge die Zeichenfolge zur Antwort hinzu.
Gib die Antwort zurück; sie ist bereits sortiert, da die erste Lücke das höchstwertige Bit ist.

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

Backtracking mit einer Palindromtabelle

Idee

Das erste Stück ist ein palindromisches Präfix s[0..end], und den Rest aufzuteilen ist dasselbe Problem ab end+1. Daher probiert backtrack(start) jedes end aus, für das s[start..end] ein Palindrom ist, fügt das Stück hinzu, ruft sich rekursiv auf und entfernt es wieder. Jeder Zweig endet mit einer Antwort, da ein einzelner Buchstabe ein Palindrom ist, daher richtet sich der Aufwand nach der Ausgabegröße: Bei abcdefghijk durchläuft die Suche einen Pfad.

Ob s[start..end] ein Palindrom ist, wird in vielen Zweigen geprüft. Lies den Wert daher aus einer Tabelle ab: s[i..j] ist eins, wenn s[i] == s[j] gilt und das Innere s[i+1..j-1] eins ist, oder das Stück höchstens 2 Buchstaben hat.

Wenn du end vom letzten Index abwärts ausprobierst, erhältst du eine sortierte Ausgabe. Zwei Aufteilungen mit unterschiedlichen ersten Stücken stimmen bis zum Ende des kürzeren Stücks überein; dort steht beim kürzeren | und beim längeren ein Buchstabe, daher steht das längere erste Stück in der Sortierung zuerst.

Algorithmus

Fülle pal[i][j] für i von n-1 abwärts bis 0: s[i] == s[j] und entweder j-i < 2 oder pal[i+1][j-1].
Schreibe backtrack(start). Wenn start gleich n ist, füge die aktuellen Teile mit | zusammen und speichere den String.
Andernfalls durchlaufe end von n-1 abwärts bis start und überspringe den Wert, wenn pal[start][end] nicht zutrifft.
Füge s[start..end] zu den Teilen hinzu, rufe backtrack(end+1) auf und entferne dann das Teil.
Rufe backtrack(0) auf und gib die gespeicherten, bereits sortierten Aufteilungen zurück.

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

Stolperfallen und Grenzfälle

Zuerst das kürzeste Stück auszuprobieren. Die Teilungen sind richtig, aber die Reihenfolge ist falsch: a|a|b vor aa|b.
Am Ende mit einem Vergleich zu sortieren, der Sprach- oder Gebietsschema-Regeln befolgt, wodurch | vor den Buchstaben stehen kann. Vergleiche Zeichencodes oder erzeuge die Teilungen in der richtigen Reihenfolge.
Die Palindromtabelle zu füllen, während i aufsteigt. pal[i+1][j-1] wird dann gelesen, bevor es berechnet wurde; fülle i ab n-1 absteigend.
Ein inklusives end mit einem exklusiven Ende eines Teilstrings zu vermischen. Das Stück s[start..end] hat end-start+1 Buchstaben.
Die gemeinsam genutzte Liste der Stücke statt des zusammengefügten Strings zu speichern. Die Suche verändert diese Liste fortlaufend, sodass am Ende jeder gespeicherte Eintrag gleich ist.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität der Palindrompartitionierung?

Bei einer Zeichenfolge aus gleichen Buchstaben sind alle 2^(n-1) Aufteilungen Lösungen, jede bis zu 2n-1 Zeichen lang: O(n × 2^n). Keine Methode ist schneller, da das Ausgeben der Lösung ebenso viel kostet. Die Palindromtabelle benötigt O(n²) Zeit und Speicherplatz, die Rekursion O(n).

Wie viele Palindromzerlegungen kann ein String haben?

Höchstens 2^(n-1), eine für jede Möglichkeit, auszuwählen, welche der n-1 Lücken geschnitten werden. Eine Zeichenkette aus gleichen Buchstaben erreicht diese Grenze: 1,024 Aufteilungen bei 11 Buchstaben. Eine Zeichenkette ohne wiederholte Buchstaben hat genau eine Aufteilung, bei der jeder Buchstabe für sich steht.

Ist Palindrome Partitioning dynamische Programmierung oder Backtracking?

Es verwendet beides. Das Auflisten von bis zu 2^(n-1) Aufteilungen erfordert eine Suche, die jede Aufteilung Stück für Stück aufbaut: Backtracking. Die dynamische Programmierung liefert die Ja-Nein-Tabelle der palindromischen Teilzeichenfolgen, die die Suche ausliest und die einmal in O(n²) ausgefüllt wird.

def partition(s):
    # Schreibe hier den Code

Test #1

Test #2

Argument

s = "aab"

Erwartete Ausgabe

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