Word Search II: trie + backtracking op een grid

Word Search II (LeetCode 212): gegeven een m × n-bord met tekens en een woordenlijst, vind je alle woorden die kunnen worden gevormd door opeenvolgende aangrenzende cellen (horizontaal of verticaal), waarbij elke cel slechts één keer mag worden gebruikt. Dit is moeilijker dan Word Search I (één woord), omdat we alle overeenkomende woorden tegelijk moeten vinden — Word Search I naïef uitvoeren voor elk woord kost O(W × m × n × 4^L), wat te traag is.

Door alle doelwoorden in een trie in te voegen en vervolgens DFS-backtracking op het bord uit te voeren, kunnen we alle woorden tegelijk zoeken. Bij elke bordcel controleren we niet: 'vormt dit pad mijn doelwoord?', maar: 'komt dit pad overeen met een prefix in de trie?'. Zodra een trie-prefix niet meer overeenkomt, snoeien we de volledige DFS-tak — zo vermijden we dubbel werk voor alle woorden die dat prefix delen.

Voeg alle woorden in een trie in. Sla het volledige woord op in de bladknoop (in node.word) in plaats van alleen een booleaanse waarde, zodat je het woord bij een volledige overeenkomst tijdens het backtracken direct aan de resultaten kunt toevoegen zonder het teken voor teken opnieuw op te bouwen.

Start DFS vanaf elke cel op het bord. Doe bij elke stap het volgende: (1) controleer of het teken van de huidige cel als kind bestaat in de huidige trieknoop; (2) zo ja, markeer de cel als bezocht (zet deze op een sentinelwaarde zoals '#') en roep de functie aan voor de 4 buren; (3) herstel de cel na de recursieve aanroep (maak de markering ongedaan). Voeg het woord aan de resultaten toe wanneer een trieknoop een niet-None word heeft en zet het vervolgens op None om duplicaten te voorkomen.

Tijd: O(m × n × 4^L), waarbij L de maximale woordlengte is. Voor elk van de m×n startcellen verkent DFS maximaal 4^L paden. De trie snoeit paden die met geen enkel woordprefix overeenkomen, waardoor het in de praktijk veel sneller is. De trie opbouwen kost O(W × L), waarbij W het aantal woorden is. Ruimte: O(W × L) voor de trie plus O(L) voor de diepte van de recursiestack.

Verwijder na het vinden van een woord de bladknoop uit de trie (zet niet alleen het woord op null) als de knoop geen kinderen heeft. Zo voorkom je dat volgende DFS-aanroepen dode takken opnieuw bezoeken. Wanneer de kinderen van een knoop na het vinden van het woord leeg zijn geworden, verwijder je de knoop uit de kinddictionary van de ouder. Deze optimalisatie is belangrijk wanneer veel woorden lange prefixen delen.

Het volledige woord opslaan in de bladknoop van de trie (in plaats van het opnieuw opbouwen vanuit het DFS-pad) heeft twee voordelen: (1) ophalen van het woord in O(1) wanneer een overeenkomst wordt gevonden, in plaats van padreconstructie in O(L); (2) node.word = None instellen nadat het woord is gevonden zorgt voor een nette deduplicatie in O(1), zonder een aparte verzameling resultaten. Vooral voor Word Search II is het voorkomen van duplicaten belangrijk, omdat hetzelfde woord theoretisch via verschillende paden kan worden gevonden.

In plaats van een aparte visited-verzameling (die O(m × n) ruimte per DFS-pad zou vereisen), markeren we cellen direct door hun teken te vervangen door een sentinelwaarde zoals '#'. Nadat DFS terugkeert, herstellen we het oorspronkelijke teken. Deze techniek: (1) gebruikt O(1) extra ruimte per cel; (2) voorkomt automatisch dat een cel binnen één pad opnieuw wordt bezocht; (3) is volledig transparant voor de trie-doorloop, omdat '#' nooit in de trie voorkomt.

Belangrijke randgevallen: (1) dubbele woorden in de woordenlijst — sla ze op in een verzameling, of gebruik de truc node.word = None om duplicaten in de resultaten te voorkomen; (2) zeer lange woorden die de bordafmetingen overschrijden — ze kunnen niet worden gevormd, maar DFS handelt dit vanzelf af doordat er geen aangrenzende cellen meer zijn; (3) een bord met één cel — alleen woorden van één teken kunnen worden gevonden; (4) hetzelfde woord dat via verschillende paden kan worden gevonden — de truc node.word = None voorkomt dubbel tellen.

Naïeve aanpak: voer voor elk van de W woorden Word Search I uit: O(W × m × n × 4^L). Met de trie worden alle woorden tegelijk gezocht: O(m × n × 4^L), ongeacht W. Voor W=1000 woorden van lengte 10 op een bord van 10×10 is de naïeve aanpak 1000× langzamer dan de trie-aanpak. De trie fungeert als een gedeeld prefixfilter dat de kosten over alle woorden verdeelt — een klassiek voorbeeld van het gebruik van een gegevensstructuur om een asymptotische verbetering te bereiken.

Volledige oplossing voor Word Search II: bouw een trie met de woorden en sla de woordtekenreeks op in de bladknoop. Voer voor elke bordcel DFS uit: controleer of het huidige teken in de huidige trieknoop voorkomt, markeer de cel als '#', roep de functie aan voor de 4 buren en herstel de cel. Voeg het woord aan de resultaten toe wanneer node.word niet null is en zet het vervolgens op null. Snoei optioneel lege trietakken na gebruik. Geef de resultatenlijst terug. Tijd: O(m×n×4^L), ruimte: O(W×L) voor de trie + O(L) voor de recursie.

In deze les heb je geleerd dat Word Search II een trie gebruikt om tegelijk naar meerdere woorden te zoeken met gedeeld snoeien op prefixen, dat het opslaan van de woordtekenreeks in de bladknoop van de trie ophalen in O(1) en eenvoudige deduplicatie mogelijk maakt door de waarde na het vinden op None te zetten, en dat het direct markeren van bezochte cellen met '#' O(m×n) extra ruimte per DFS-pad voorkomt. Hiermee rond je de cursus Tries and String Algorithms af — je hebt een van de krachtigste tekenreeks-specifieke gegevensstructuren voor technische sollicitatiegesprekken onder de knie.