Lad os først se på begrænsningerne på problemet. Du vil gemme en ordliste for et spil i en datastruktur, der effektivt understøtter "anagram"-problemet. Det vil sige, givet et "rack" på n bogstaver, hvad er alle de n-eller-færre-bogstavsord i ordlisten, der kan laves fra det stativ. ordlisten vil være på omkring 400.000 ord, og det er sandsynligvis omkring en til ti meg strengdata, når den er ukomprimeret.
En prøve er den klassiske datastruktur, der bruges til at løse dette problem, fordi den kombinerer både hukommelseseffektivitet med søgeeffektivitet. Med en ordliste på omkring 400.000 ord af rimelig længde burde du være i stand til at gemme forsøget i hukommelsen. (I modsætning til at gå med en b-tree-løsning, hvor du beholder det meste af træet på disken, fordi det er for stort til at passe i hukommelsen på én gang.)
En trie er dybest set ikke mere end et 26-ært træ (forudsat at du bruger det romerske alfabet), hvor hver node har et bogstav og en ekstra bit på hver node, der siger, om det er slutningen af ordet.
Så lad os skitsere datastrukturen:
klasse TrieNode{ char Letter; bool IsEndOfWord; Liste børn; } Dette er selvfølgelig kun en skitse; du vil sikkert gerne få disse til at have ordentlige ejendomstilbehør og konstruktører og lignende. Desuden er en flad liste måske ikke den bedste datastruktur; måske en slags ordbog er bedre. Mit råd er at få det til at virke først og derefter måle dets ydeevne, og hvis det er uacceptabelt, så eksperimentere med at lave ændringer for at forbedre dets ydeevne.
Du kan starte med et tomt forsøg:
TrieNode root =new TrieNode('^', false, new List()); Det vil sige, at dette er "rod"-knudepunktet, der repræsenterer begyndelsen af et ord.
Hvordan tilføjer du ordet "AA", det første ord i Scrabble-ordbogen? Nå, lav først en node til det første bogstav:
root.Children.Add('A', false, new List()); Okay, vores forsøg er nu
^|A Tilføj nu en node for det andet bogstav:
root.Children[0].Children.Add(new trieNode('A', true, new List())); Vores forsøg er nu
^|A|A$ -- vi noterer slutningen af ordflag med $ Store. Antag nu, at vi vil tilføje AB. Vi har allerede en node for "A", så føj "B$" noden til den:
root.Children[0].Children.Add(new trieNode('B', true, new List()); og nu har vi
^ | A / \ A$ B$ Fortsæt sådan. I stedet for at skrive "root.Children[0]..." vil du selvfølgelig skrive en løkke, der søger i forsøget for at se, om den node, du ønsker, findes, og hvis ikke, opret den.
For at gemme din prøve på disk -- ærligt talt ville jeg bare gemme ordlisten som en almindelig tekstfil og genopbygge prøven, når du har brug for det. Det bør ikke tage mere end 30 sekunder eller deromkring, og så kan du genbruge forsøget i hukommelsen. Hvis du ønsker at gemme prøveversionen i et eller andet format, der er mere som en prøveversion, burde det ikke være svært at finde på et serialiseringsformat.
For at søge i trien for at matche et stativ, er ideen at udforske alle dele af trien, men at beskære de områder, hvor stativet umuligt kan matche. Hvis du ikke har nogen "A" på stativet, er der ingen grund til at gå ned i nogen "A"-knude. Jeg skitserede søgealgoritmen i dit tidligere spørgsmål.
Jeg har en implementering af et vedholdende forsøg i funktionel stil, som jeg har tænkt mig at blogge om i et stykke tid, men som jeg aldrig nåede. Hvis jeg til sidst poster det, vil jeg opdatere dette spørgsmål.