Partizionamento palindromico II

Palindrome Partitioning II chiede di trovare, data una stringa s, il numero minimo di tagli necessari affinché ogni sottostringa della partizione sia un palindromo. Per 'aab', un taglio produce ['aa', 'b'], quindi la risposta è 1. Per 'a' la risposta è 0 (è già un palindromo). Questo problema combina due fasi di DP: prima si precalcola quali sottostringhe sono palindromi, poi si usa una DP 1D per trovare il numero minimo di tagli.

Per prima cosa si costruisce is_pal[i][j] = True se s[i..j] è un palindromo, usando la DP su intervalli. Questa procedura richiede O(n²) di tempo e O(n²) di spazio. In alternativa, l'espansione attorno al centro riempie la stessa tabella in O(n²) di tempo. Questa tabella è necessaria perché la DP 1D dei tagli interrogherà ripetutamente is_pal[i][j]: il precalcolo evita di ripetere i controlli dei palindromi all'interno del ciclo della DP dei tagli.

Si definisca cuts[i] come il numero minimo di tagli per partizionare s[0..i]. Se s[0..i] è già un palindromo, cuts[i] = 0. Altrimenti si prova ogni divisione: per ogni j da 0 a i-1, se s[j+1..i] è un palindromo, allora cuts[i] = min(cuts[i], cuts[j] + 1). La domanda è: cosa succede se l'ultimo pezzo della partizione è s[j+1..i]? In tal caso servono cuts[j] tagli per il prefisso, più un ulteriore taglio.

Analizziamo 'aab'. Tabella dei palindromi: 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. Tagli: cuts[0]=0 ('a' è un palindromo), cuts[1]=0 ('aa' è un palindromo), cuts[2]: 'aab' non è un palindromo; si prova j=1: is_pal[2][2]=T, quindi cuts[2] = cuts[1]+1 = 1. Risposta: 1.

La fase 1 (tabella dei palindromi) richiede O(n²) di tempo e O(n²) di spazio. La fase 2 (DP dei tagli) ha un ciclo esterno sulle n posizioni e un ciclo interno sugli n punti di divisione, quindi richiede anch'essa O(n²) di tempo. Complessivamente: O(n²) di tempo, O(n²) di spazio. Lo spazio può essere ridotto a O(n) per l'array dei tagli, ma la tabella dei palindromi richiede comunque O(n²). Nei colloqui ci si aspetta O(n²): una soluzione O(n) che usa l'algoritmo di Manacher va oltre l'ambito tipico.

Anziché usare l'approccio della DP su intervalli per la tabella dei palindromi, è possibile riempire is_pal usando l'espansione attorno al centro. Per ogni posizione centrale, si procede verso l'esterno e si segnano tutti i palindromi trovati. La procedura richiede comunque O(n²) di tempo e O(n²) di spazio, ma nella pratica potrebbe essere più veloce grazie a un migliore comportamento della cache. Entrambi gli approcci sono validi nei colloqui.

Palindrome Partitioning I (un problema correlato) chiede di enumerare TUTTE le partizioni valide in cui ogni sottostringa è un palindromo. Si usa il backtracking, con la tabella dei palindromi precalcolata come criterio di potatura. A differenza della DP dei tagli minimi, che conta le soluzioni, questo approccio ne enumera un numero esponenziale e richiede una strategia completamente diversa.

Un trucco comune consiste nell'inizializzare cuts[i] = i anziché inf, poiché nel caso peggiore per s[0..i] si separa ogni carattere, ottenendo i tagli. In questo modo non è necessario verificare la presenza di inf nel codice. Quando is_pal[0][i] è vero, il valore viene sostituito con 0. Questa inizializzazione chiarisce il limite superiore del numero di tagli e semplifica leggermente il codice.

Una variante elegante riempie contemporaneamente la tabella dei palindromi e la DP dei tagli. Mentre si espandono i palindromi a partire da ciascun centro, si aggiorna immediatamente l'array cuts. Per un palindromo s[l..r], è possibile aggiornare cuts[r] = min(cuts[r], (cuts[l-1]+1 if l > 0 else 0)). Si evita così un passaggio separato O(n²) sulla tabella e l'implementazione potrebbe risultare più semplice durante un colloquio con poco tempo a disposizione.

Principali casi limite per Palindrome Partitioning II: (1) una stringa di un solo carattere restituisce 0 tagli; (2) una stringa che è già un palindromo restituisce 0 tagli; (3) una stringa con tutti caratteri distinti richiede n-1 tagli; (4) una stringa composta dallo stesso carattere ripetuto (ad esempio 'aaaa') richiede 0 tagli, poiché l'intera stringa è un palindromo. Verifichi sempre che la soluzione gestisca correttamente l'uscita anticipata is_pal[0][i] = True.

Quando presenta questo problema in un colloquio, inizi dall'approccio in due fasi: prima costruisca la tabella dei palindromi, quindi esegua una DP 1D sull'array dei tagli. Spieghi a parole la ricorrenza prima di scrivere il codice. Menzioni che la tabella dei palindromi contiene O(n²) elementi e che ciascuno viene calcolato in O(1) usando la ricorrenza della DP su intervalli. Prima di scrivere la soluzione completa, ripercorra sempre l'esempio di traccia per dimostrare la correttezza anche sotto pressione.

In questa lezione ha imparato: il palindrome partitioning II usa due fasi di DP: prima si precalcola la tabella dei palindromi, poi si esegue la DP 1D dei tagli, la ricorrenza dei tagli è cuts[i] = min(cuts[j-1] + 1) per ogni j per cui s[j..i] è un palindromo e la complessità complessiva è O(n²) di tempo e O(n²) di spazio. Nel prossimo argomento affronteremo il problema Burst Balloons, che usa un ingegnoso approccio di DP inversa su intervalli.