Of course, rather than writing "root.Children." you'll write a loop that searches the trie to see if the node you want exists, and if not, create it.
We already have a node for "A", so add to it the "B$" node: (new trieNode('B', true, new List()) Now add a node for the second letter: (new trieNode('A', true, new List())) Ī$ - we notate the end of word flag with $
How do you add the word "AA", the first word in the Scrabble dictionary? Well, first make a node for the first letter: ('A', false, new List())
That is, this is the "root" trie node that represents the beginning of a word. You can start with an empty trie: TrieNode root = new TrieNode('^', false, new List()) My advice is to get it working first, and then measure its performance, and if it is unacceptable, then experiment with making changes to improve its performance. Also, maybe a flat list is not the best data structure maybe some sort of dictionary is better. This of course is just a sketch you'd probably want to make these have proper property accessors and constructors and whatnot. So let's sketch the data structure: class TrieNode (As opposed to going with a b-tree sort of solution where you keep most of the tree on disk because it is too big to fit in memory all at once.)Ī trie is basically nothing more than a 26-ary tree (assuming you're using the Roman alphabet) where every node has a letter and one additional bit on each node that says whether it is the end of the word. With a word list of about 400K words of reasonable length you should be able to keep the trie in memory. the word list will be about 400K words, and so is probably about one to ten megs of string data when uncompressed.Ī trie is the classic data structure used to solve this problem because it combines both memory efficiency with search efficiency. That is, given a "rack" of n letters, what are all the n-or-fewer-letter words in the word list that can be made from that rack. You want to store a word list for a game in a data structure that efficiently supports the "anagram" problem. How do I use C# to search for words using the Trie depending on letters and wildcards?Īny help is very much appreciated, I’m still a beginner with C# and MySQL so please be gentleįirst off, let's look at the constraints on the problem.How do I store the Trie for fast and easy access? (UPDATE: So I can trash my database).How do I build a Trie from the database? (UPDATE: I want to generate a Trie using the words already in my database, after that's done I'm not going to use the database for word matching any more).Having a plan is no good if you can’t execute it, this is what I need help with: Building a Trie with all the words from the database so I can do a fast and accurate search for words depending on user letter/wildcard input.Using ASP.NET with C# as server-side programming language.Using MySQL database with a dictionary containing over 400k words.Users get word suggestions by typing in any amount of letters and 0 or more wildcards.Build a mobile web application where the user can get help finding words to play when playing scrabble.