Palindrome Partitioning

Q: Qual è la complessità temporale della partizione in palindromi?

Su una stringa composta da lettere tutte uguali, tutti gli 2^(n-1) tagli sono soluzioni, ciascuna lunga al massimo 2n-1 caratteri: O(n × 2^n) . Nessun metodo può fare di meglio, perché scrivere la soluzione richiede altrettanto. La tabella dei palindromi aggiunge O(n²) di tempo e spazio, e la ricorsione O(n) .

Q: Quante partizioni palindrome può avere una stringa?

Al massimo 2^(n-1) , una per ogni modo di scegliere quali dei n-1 spazi tagliare. Una stringa composta da lettere uguali raggiunge questo limite: 1.024 suddivisioni per 11 lettere. Una stringa senza lettere ripetute ha esattamente una suddivisione, con ogni lettera da sola.

Q: La partizione palindroma si risolve con la programmazione dinamica o con il backtracking?

Usa entrambi. Elencare fino a 2^(n-1) suddivisioni richiede una ricerca che costruisce ogni suddivisione pezzo per pezzo: backtracking. La programmazione dinamica fornisce la tabella sì o no delle sottostringhe palindromiche che la ricerca consulta, compilata una sola volta in O(n²) .

MedioBacktracking Programmazione dinamica

+10

Un palindromo si legge allo stesso modo da sinistra a destra e da destra a sinistra. Suddividi la stringa s in uno o più pezzi, in modo che ogni pezzo sia un palindromo, e restituisci tutti i modi per farlo.

Scrivi ogni suddivisione come i suoi pezzi in ordine, separati da |: dividendo aab in a, a e b si ottiene a|a|b. Restituisci le suddivisioni in ordine crescente, confrontando i codici dei caratteri, così che | venga dopo ogni lettera minuscola.

Funzione

partition(s: string) → string-array

sstring: la stringa di lettere minuscole da tagliare
Restituiscestring-array: ogni suddivisione di s in palindromi, scritta con | tra i pezzi, in ordine crescente

Vincoli

1 ≤ s.length ≤ 11
s contiene solo lettere inglesi minuscole.
Una stringa di 11 lettere uguali ha 1.024 suddivisioni, la risposta più grande.

Esempi

Input: s = "aab"
Output: ["aa|b", "a|a|b"]
Spiegazione: Solo aa|b e a|a|b hanno tutte le parti palindromiche; a|ab non supera il test su ab. aa|b viene prima nell’ordinamento: al secondo carattere ha a, mentre l’altro ha |, che viene dopo ogni lettera nell’ordinamento.

Input: s = "abba"
Output: ["abba", "a|bb|a", "a|b|b|a"]
Spiegazione: abba è di per sé un palindromo, quindi la stringa non suddivisa è una suddivisione e viene ordinata per prima: il suo secondo carattere è una lettera. a|bb|a viene prima di a|b|b|a: al quarto carattere ha b, mentre l'altra ha |.

Per approfondire

Riesci a trovare il numero minimo di tagli necessari per dividere s in palindromi, per stringhe lunghe fino a 2.000 caratteri?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Ciascuno degli n-1 spazi tra le lettere viene tagliato oppure no, quindi ci sono 2^(n-1) suddivisioni, e tutte possono essere risposte. Non puoi ridurre la dimensione dell'output, ma puoi saltare le suddivisioni che non funzionano: costruisci ogni suddivisione da sinistra a destra, separa solo le parti palindromiche e leggi i palindromi da una tabella compilata una sola volta.

Prova ogni serie di tagli

Intuizione

Numera le suddivisioni con gli interi da 0 a 2^(n-1)-1, dove ogni bit indica se viene tagliato uno spazio. Conserva una suddivisione se ogni pezzo è un palindromo.

Se il primo spazio corrisponde al bit più significativo, contando verso l’alto si elencano le suddivisioni in ordine crescente. Per due numeri, il bit più significativo in cui differiscono corrisponde al primo spazio in cui uno taglia e l’altro no. Prima di quel punto le stringhe sono uguali; lì, il numero più piccolo ha una lettera e quello più grande ha |, che viene dopo ogni lettera nell’ordinamento. Per aab, 1 dà aa|b e 3 dà a|a|b.

Con 11 lettere, si tratta di 1.024 maschere, ciascuna di 11 lettere. Lo spreco è nelle suddivisioni scartate: abcdefghijk ne genera 1.024 per trovarne una valida.

Algoritmo

Fai scorrere mask da 0 a 2^(n-1)-1.
Scorri le lettere; termina una parte dopo la lettera i quando i è l'ultimo indice o il bit n-2-i di mask è impostato.
Controlla ogni parte con due puntatori che si muovono verso l'interno.
Se ogni parte è un palindromo, unisci le parti con | e aggiungi la stringa alla risposta.
Restituisci la risposta; è già ordinata perché il primo separatore è il bit più significativo.

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 con una tabella dei palindromi

Intuizione

Il primo pezzo è un prefisso palindromo s[0..end], e suddividere il resto è lo stesso problema a partire da end+1. Quindi backtrack(start) prova ogni end per cui s[start..end] è un palindromo, aggiunge il pezzo, richiama ricorsivamente la funzione e lo rimuove. Ogni ramo termina con una risposta, poiché una singola lettera è un palindromo, quindi il lavoro è proporzionale alla dimensione dell'output: per abcdefghijk la ricerca percorre un solo percorso.

La verifica che s[start..end] sia un palindromo si ripete in molti rami, quindi leggila da una tabella: s[i..j] vale uno quando s[i] == s[j] e la parte interna s[i+1..j-1] vale uno, oppure quando il pezzo ha al massimo 2 lettere.

Provare end dall'indice finale verso l'inizio produce un output ordinato. Due suddivisioni con pezzi iniziali diversi coincidono fino alla fine del pezzo più corto; lì il più corto ha | e il più lungo ha una lettera, quindi il pezzo iniziale più lungo viene prima nell'ordinamento.

Algoritmo

Riempi pal[i][j] per i da n-1 fino a 0: s[i] == s[j] e j-i < 2 oppure pal[i+1][j-1].
Scrivi backtrack(start). Se start è uguale a n, unisci i segmenti correnti con | e salva la stringa.
Altrimenti, scorri end da n-1 fino a start e salta l'elemento se pal[start][end] è falso.
Aggiungi s[start..end] ai segmenti, chiama backtrack(end+1), poi rimuovi il segmento.
Chiama backtrack(0) e restituisci le suddivisioni salvate, già ordinate.

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

Trappole e casi limite

Provare prima il pezzo più corto. Le divisioni sono corrette, ma l’ordine è sbagliato: a|a|b prima di aa|b.
Ordinare alla fine con un confronto che segue le regole linguistiche o locali, che può posizionare | prima delle lettere. Confronta i codici dei caratteri oppure genera le divisioni nell’ordine corretto.
Riempire la tabella dei palindromi aumentando i. In tal caso pal[i+1][j-1] viene letto prima di essere calcolato; riempi la tabella facendo scendere i da n-1.
Confondere un end inclusivo con la fine esclusiva di una sottostringa. Il pezzo s[start..end] ha end-start+1 lettere.
Salvare l’elenco condiviso dei pezzi invece della stringa concatenata. La ricerca continua a modificare quell’elenco, quindi tutte le voci salvate finiscono per essere uguali.

Domande frequenti3

Qual è la complessità temporale della partizione in palindromi?

Su una stringa composta da lettere tutte uguali, tutti gli 2^(n-1) tagli sono soluzioni, ciascuna lunga al massimo 2n-1 caratteri: O(n × 2^n). Nessun metodo può fare di meglio, perché scrivere la soluzione richiede altrettanto. La tabella dei palindromi aggiunge O(n²) di tempo e spazio, e la ricorsione O(n).

Quante partizioni palindrome può avere una stringa?

Al massimo 2^(n-1), una per ogni modo di scegliere quali dei n-1 spazi tagliare. Una stringa composta da lettere uguali raggiunge questo limite: 1.024 suddivisioni per 11 lettere. Una stringa senza lettere ripetute ha esattamente una suddivisione, con ogni lettera da sola.

La partizione palindroma si risolve con la programmazione dinamica o con il backtracking?

Usa entrambi. Elencare fino a 2^(n-1) suddivisioni richiede una ricerca che costruisce ogni suddivisione pezzo per pezzo: backtracking. La programmazione dinamica fornisce la tabella sì o no delle sottostringhe palindromiche che la ricerca consulta, compilata una sola volta in O(n²).

def partition(s):
    # Scrivi il codice qui

Test #1

Test #2

Argomento

s = "aab"

Output atteso

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