Prefixsökning och Starts-With

För att implementera autocomplete går du till prefixets slutnod och gör sedan en DFS eller BFS från den noden för att samla in alla ord som grenar ut från den. Lägg till prefixet framför varje insamlat suffix för att återskapa de fullständiga orden. Detta tar O(p + W) tid, där W är det totala antalet tecken i alla matchande ord.

För sorterade autocomplete-förslag går du igenom barnen i alfabetisk ordning under DFS, genom att iterera över sorted(node.children.items()). Eftersom barnen lagras i en dictionary tillkommer overhead på O(ALPHABET_SIZE × depth), men resultaten garanteras komma i lexikografisk ordning. En arraybaserad trie går alltid igenom barnen i alfabetisk ordning, eftersom indexen 0–25 är ordnade.

För topp-k-förslag efter frekvens utökar du varje nod med ett antal som anger hur många gånger ordet som slutar där har sökts efter. När du samlar in förslag använder du en max-heap med storleken k. Detta minskar resultatmängden från DFS, O(W), till O(k) utan att materialisera alla matchningar. Sökmotorer i verkligheten kombinerar triegenomgång av prefix med frekvensdata för att snabbt skapa relevanta förslag.

LeetCode 208, 'Implement Trie (Prefix Tree)', kräver exakt följande: insert(word), search(word) som returnerar ett booleskt värde för exakt matchning, och startsWith(prefix) som returnerar ett booleskt värde för prefixmatchning. Detta är den klassiska trie-implementeringen. Kom ihåg: search kräver is_end=True; startsWith kräver endast att prefixvägen finns.

En elegant genväg är att lagra trien som nästlade dictionary-objekt med en särskild sentinel-nyckel, till exempel '#', för att markera ordslut. Då behövs ingen TrieNode-klass. Detta är kompakt och passar bra i intervjuer, men är något mindre läsbart än explicita TrieNode-objekt. Båda implementationerna är godtagbara; dictionary-versionen går snabbare att skriva under tidspress.

För att hitta det längsta gemensamma prefixet i en lista med strängar infogar du alla strängar i trien och går sedan från roten längs den enda väg som finns så länge som: (1) den aktuella noden har exakt ett barn och (2) is_end är False. Stanna så snart något av villkoren inte längre gäller. Den följda vägen är det längsta gemensamma prefixet.

Replace Words (LeetCode 648): givet en dictionary med rotord och en mening ska du ersätta varje ord i meningen med det kortaste matchande rotordet från dictionaryn. Infoga alla rotord i en trie. För varje ord i meningen går du igenom trien tills slutet på ett rotord hittas — returnera då det rotordet som ersättning. Om inget rotord matchar behåller du det ursprungliga ordet. Detta körs på O(total chars) jämfört med O(n × m) för brute force.

Map Sum (LeetCode 677): infoga nyckel-värde-par och returnera summan av alla värden vars nycklar har ett givet prefix. Utöka varje TrieNode med ett val-fält. Vid insert går du till slutet och anger värdet; vid sum-frågor går du till prefixets slutnod och summerar alla val-fält under den med DFS. Alternativt kan du lagra den kumulativa summan i varje nod under insättningen för frågor med O(p)-komplexitet.

I produktionssystem för autocomplete är det opraktiskt att returnera alla ord med ett visst prefix när tusentals ord matchar. Använd i stället en max-heap med storleken k under DFS-genomgången: håll reda på de k ord med högst poäng som hittats hittills. Avsluta DFS-grenar tidigt om de omöjligen kan innehålla ett ord bland de k bästa (beskärning utifrån en övre gräns för poängen). Då blir tidskomplexiteten O(p + k × log k) per fråga för k förslag — mycket bättre än att samla in alla träffar.

I den här lektionen lärde du dig: starts_with går igenom prefixvägen och returnerar True om den finns — någon is_end-kontroll behövs inte, autocomplete-DFS samlar in alla ord från prefixets slutnod genom att lägga till tecken när den går nedåt, och att utöka noder med antal eller värden möjliggör summationsfrågor och top-k-förslag. Nästa steg är att lägga till matchning med jokertecken och reguljära uttryck i trien.