Word Search II: trie e backtracking su griglia

Word Search II (LeetCode 212): dato un tabellone di caratteri m × n e un elenco di parole, trovare tutte le parole che possono essere formate da celle adiacenti in sequenza (orizzontalmente o verticalmente), dove ogni cella può essere utilizzata una sola volta. È più difficile di Word Search I (una sola parola), perché è necessario trovare tutte le parole corrispondenti simultaneamente: eseguire ingenuamente Word Search I per ogni parola ha complessità O(W × m × n × 4^L), troppo lenta.

Inserire tutte le parole cercate in un trie e poi eseguire il backtracking DFS sul tabellone consente di cercare tutte le parole simultaneamente. In ogni cella del tabellone, invece di verificare «questo percorso forma la mia parola cercata?», si verifica «questo percorso corrisponde a un prefisso nel trie?». Non appena un prefisso del trie non corrisponde, si pota l'intero ramo DFS, evitando lavoro ridondante tra tutte le parole che condividono quel prefisso.

Si inseriscano tutte le parole in un trie. Si memorizzi la parola completa nel nodo foglia (in node.word) anziché solo un valore booleano, così, quando durante il backtracking viene trovata una corrispondenza completa, è possibile aggiungere immediatamente la parola ai risultati senza ricostruirla carattere per carattere.

Si avvii una DFS da ogni cella del tabellone. A ogni passo: (1) si verifichi se il carattere della cella corrente esiste come figlio nel nodo corrente del trie; (2) in caso affermativo, si contrassegni la cella come visitata (impostandola su un sentinella come '#') e si ricorra sui 4 vicini; (3) dopo la ricorsione, si ripristini la cella (rimuovendo il contrassegno). Quando un nodo del trie ha un word diverso da None, lo si aggiunga ai risultati e lo si imposti a None per evitare duplicati.

Tempo: O(m × n × 4^L), dove L è la lunghezza massima delle parole. Per ciascuna delle m×n celle iniziali, la DFS esplora fino a 4^L percorsi. Il trie pota i percorsi che non corrispondono ad alcun prefisso di parola, quindi nella pratica è molto più veloce. La costruzione del trie è O(W × L), dove W è il numero di parole. Spazio: O(W × L) per il trie, oltre a una profondità dello stack di ricorsione pari a O(L).

Dopo aver trovato una parola, si rimuova il nodo foglia dal trie (non ci si limiti a impostare la parola a null) se non ha figli. Questo impedisce di attraversare nuovamente rami inattivi nelle chiamate DFS successive. Quando i figli di un nodo diventano vuoti dopo il ritrovamento della parola, si rimuova il nodo dal dizionario dei figli del genitore. Questa ottimizzazione è significativa quando molte parole condividono prefissi lunghi.

Memorizzare la parola completa nel nodo foglia del trie (anziché ricostruirla dal percorso DFS) offre due vantaggi: (1) recupero della parola in O(1) quando viene trovata una corrispondenza, invece della ricostruzione del percorso in O(L); (2) impostare node.word = None dopo aver trovato la parola consente una deduplicazione pulita in O(1), senza bisogno di un set dei risultati separato. In Word Search II, in particolare, impedire i duplicati è importante perché in teoria la stessa parola potrebbe essere trovata seguendo percorsi diversi.

Anziché utilizzare un set visited separato (che richiederebbe spazio O(m × n) per ogni percorso DFS), si contrassegnano le celle direttamente nella griglia sostituendo il loro carattere con un sentinella come '#'. Al termine della DFS, si ripristina il carattere originale. Questa tecnica: (1) utilizza O(1) di spazio aggiuntivo per cella; (2) impedisce automaticamente di visitare nuovamente una cella all'interno dello stesso percorso; (3) è completamente trasparente all'attraversamento del trie, poiché '#' non sarà mai presente nel trie.

Casi limite importanti: (1) parole duplicate nell'elenco: memorizzarle in un set oppure utilizzare il trucco node.word = None per impedire duplicati nei risultati; (2) parole molto lunghe che superano le dimensioni del tabellone: non possono essere formate, ma la DFS gestisce naturalmente il caso quando esaurisce le celle adiacenti; (3) tabellone a cella singola: è possibile trovare solo parole di un carattere; (4) stessa parola trovabile attraverso percorsi diversi: il trucco node.word = None impedisce di conteggiarla due volte.

Approccio ingenuo: per ciascuna delle W parole, eseguire Word Search I: O(W × m × n × 4^L). Con il trie, tutte le parole vengono cercate simultaneamente: O(m × n × 4^L), indipendentemente da W. Per W=1000 parole di lunghezza 10 su un tabellone 10×10, l'approccio ingenuo è 1000 volte più lento rispetto al trie. Il trie agisce da filtro condiviso sui prefissi, ammortizzando il costo tra tutte le parole: un esempio classico di utilizzo di una struttura dati per ottenere un miglioramento asintotico.

Soluzione completa di Word Search II: costruire il trie con le parole e memorizzare la stringa della parola nella foglia. Per ogni cella del tabellone, eseguire una DFS: verificare se il carattere corrente esiste nel nodo corrente del trie, contrassegnare la cella con '#', ricorrere sui 4 vicini e ripristinare la cella. Quando node.word non è null, aggiungerlo ai risultati e impostarlo a null. Facoltativamente, potare i rami vuoti del trie dopo l'utilizzo. Restituire l'elenco dei risultati. Tempo: O(m×n×4^L), spazio: trie O(W×L) + ricorsione O(L).

Verifichi la Sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.

In questa lezione ha imparato che: Word Search II utilizza un trie per cercare simultaneamente più parole, potando i prefissi condivisi, memorizzare la stringa della parola nella foglia del trie consente di recuperarla in O(1) e di deduplicare facilmente impostandola a None dopo averla trovata e contrassegnare direttamente le celle visitate con '#' evita O(m×n) di spazio aggiuntivo per ogni percorso DFS. Con questa lezione si conclude il corso Tries and String Algorithms: ha acquisito padronanza di una delle strutture dati specifiche per le stringhe più potenti e utilizzate nei colloqui tecnici.