Word Search II: trie och backtracking i ett rutnät

Word Search II (LeetCode 212): givet ett teckenbräde med storleken m × n och en lista med ord ska du hitta alla ord som kan bildas av sekventiellt intilliggande celler (horisontellt eller vertikalt), där varje cell endast får användas en gång. Detta är svårare än Word Search I (ett enda ord), eftersom vi måste hitta alla matchande ord samtidigt — att naivt köra Word Search I för varje ord ger O(W × m × n × 4^L), vilket är för långsamt.

Genom att infoga alla målord i ett trie och sedan köra DFS-backtracking på brädet kan vi söka efter alla ord samtidigt. Vid varje brädcell kontrollerar vi i stället för ”bildar den här vägen mitt målord?” om ”matchar den här vägen ett prefix i trien?”. Så snart ett trie-prefix inte längre matchar beskär vi hela DFS-grenen — och undviker därmed överflödigt arbete för alla ord som delar prefix.

Infoga alla ord i ett trie. Lagra hela ordet i lövnoden (i node.word) i stället för bara en boolesk flagga, så att vi omedelbart kan lägga till ordet i resultatet när en fullständig träff hittas under backtracking, utan att återskapa det tecken för tecken.

Starta en DFS från varje cell på brädet. Gör följande vid varje steg: (1) kontrollera om den aktuella cellens tecken finns som ett barn i den aktuella trienoden; (2) om ja, markera cellen som besökt (sätt den till ett platshållartecken som '#'), gå rekursivt igenom de 4 grannarna; (3) återställ cellen efter rekursionen (avmarkera den). När en trienod har ett värde som inte är None i word, lägger du till det i resultatet och sätter det till None för att undvika dubbletter.

Tid: O(m × n × 4^L), där L är den maximala ordlängden. För var och en av de m×n startcellerna utforskar DFS upp till 4^L sökvägar. Trien beskär sökvägar som inte matchar något ordprefix, så i praktiken går det mycket snabbare. Att bygga trien är O(W × L), där W är antalet ord. Utrymme: O(W × L) för trien samt O(L) för rekursionsstackens djup.

Efter att ett ord hittats bör du ta bort lövnoden från trien (inte bara sätta word till null) om den saknar barn. Det förhindrar att döda grenar besöks igen i efterföljande DFS-anrop. När en nods children blir tomma efter att ordet hittats tar du bort noden ur dess förälders children-dict. Denna optimering är betydelsefull när många ord delar långa prefix.

Att lagra hela ordet i trie-lövnoden (i stället för att återskapa det från DFS-sökvägen) har två fördelar: (1) ordet kan hämtas i O(1) när en träff hittas, i stället för att återskapa sökvägen i O(L); (2) att sätta node.word = None efter att ordet hittats ger en ren deduplicering i O(1), utan behov av en separat resultatmängd. För Word Search II är det särskilt viktigt att förhindra dubbletter, eftersom samma ord i teorin kan hittas via olika sökvägar.

I stället för en separat visited-mängd, som skulle kräva O(m × n) utrymme per DFS-sökväg, markerar vi celler direkt genom att ersätta deras tecken med ett platshållartecken som '#'. När DFS returnerar återställer vi det ursprungliga tecknet. Tekniken: (1) använder O(1) extra utrymme per cell; (2) förhindrar automatiskt att cellen besöks igen under samma sökväg; (3) är helt transparent för trie-traverseringen eftersom '#' aldrig finns i trien.

Viktiga specialfall: (1) duplicerade ord i ordlistan — lagra orden i en mängd, eller använd node.word = None-tricket för att förhindra dubbletter i resultatet; (2) mycket långa ord som överskrider brädets dimensioner — de kan inte bildas, men DFS hanterar detta naturligt genom att de intilliggande cellerna tar slut; (3) bräde med en enda cell — endast ord med ett tecken kan hittas; (4) samma ord kan hittas via olika sökvägar — node.word = None-tricket förhindrar dubbelräkning.

Naiv metod: kör Word Search I för vart och ett av W ord: O(W × m × n × 4^L). Med trien söks alla ord samtidigt: O(m × n × 4^L), oavsett W. För W=1000 ord med längden 10 på ett bräde med storleken 10×10 är den naiva metoden 1000× långsammare än trie-metoden. Trien fungerar som ett gemensamt prefixfilter som fördelar kostnaden över alla ord — ett klassiskt exempel på hur en datastruktur kan ge en asymptotisk förbättring.

Fullständig lösning på Word Search II: bygg ett trie med orden och lagra ordsträngen i lövnoden. Kör DFS från varje brädcell: kontrollera om det aktuella tecknet finns i den aktuella trienoden, markera cellen som '#', gå rekursivt igenom de 4 grannarna och återställ cellen. När node.word inte är null lägger du till det i resultatet och nollar det. Du kan även välja att beskära tomma triegrenar efter användning. Returnera resultatlistan. Tid: O(m×n×4^L), utrymme: O(W×L) för trien + O(L) rekursion.

I den här lektionen lärde du dig: Word Search II använder ett trie för samtidig sökning efter flera ord med gemensam prefixbeskärning, att lagra ordsträngen i trie-lövet möjliggör O(1)-hämtning av ordet och enkel deduplicering genom att sätta det till None efter att ordet hittats, och markering av besökta celler på plats med '#' undviker O(m×n) extra utrymme per DFS-sökväg. Detta avslutar kursen Tries and String Algorithms — du har bemästrat en av de mest kraftfulla strängspecifika datastrukturerna som används i intervjuer.