A directed acyclic graph contains nodes that do not form cycles. It can be used to store strings from a word list—each letter is one node.
For search performance, an optimized tree is often the best solution. It has an initialization cost. And it requires some extra code to create. The C# version here is not optimal.
In the C# language a tree can be implemented with classes (nodes) that point to further nodes. In this simple implementation, we use a Dictionary
.
AddWord()
takes a string
argument and adds it to the tree by creating (or using existing) nodes (one per character).ContainsWord()
is similar to AddWord
, but does not add anything. It just does lookups. It returns a bool
.Add()
will add a new DictionaryNode
to the Dictionary
if one does not exist. It one already exists, it will not add another.Get()
retrieves a node from the tree from the current node—it uses a Dictionary
lookup (TryGetValue
).using System; using System.Collections.Generic; class DictionaryNodeRoot { DictionaryNode _root = new DictionaryNode(); public void AddWord(string value) { // Add nodes from string chars. DictionaryNode current = this._root; for (int i = 0; i < value.Length; i++) { current = current.Add(value[i]); } // Set state. current.SetWord(value); } public bool ContainsWord(string value) { // Get existing nodes from string chars. DictionaryNode current = this._root; for (int i = 0; i < value.Length; i++) { current = current.Get(value[i]); if (current == null) { return false; } } // Return state. return current != null && current.GetWord() != null; } } class DictionaryNode { string _word; Dictionary<char, DictionaryNode> _dict; // Slow. public DictionaryNode Add(char value) { // Add individual node as child. // ... Handle null field. if (this._dict == null) { this._dict = new Dictionary<char, DictionaryNode>(); } // Look up and return if possible. DictionaryNode result; if (this._dict.TryGetValue(value, out result)) { return result; } // Store. result = new DictionaryNode(); this._dict[value] = result; return result; } public DictionaryNode Get(char value) { // Get individual child node. if (this._dict == null) { return null; } DictionaryNode result; if (this._dict.TryGetValue(value, out result)) { return result; } return null; } public void SetWord(string word) { this._word = word; } public string GetWord() { return this._word; } } class Program { static void Main() { // Create a tree. DictionaryNodeRoot tree = new DictionaryNodeRoot(); // Add three words to the tree. tree.AddWord("dot"); tree.AddWord("net"); tree.AddWord("perls"); // Search for strings in the tree. Console.WriteLine(tree.ContainsWord("perls")); Console.WriteLine(tree.ContainsWord("nothing")); } }True False
AddWord
We add a string
char
-by-char
with a for
-loop in AddWord
. The Add method from DictionaryNode.cs
returns the newly-added or accessed node. We call Add repeatedly.
SetWord
method is used. This signals that a complete word has been reached at this node.DictionaryNode
On each node, we use a Dictionary
instance. The Dictionary
provides references to child nodes. The string
field tells us whether a complete word here exists.
Dictionary
field uses a char
key type. This is not essential. With this tree design, any value type could be used.Dictionary
for the value specified. They return the DictionaryNode
found, or null
.This tree uses Dictionary
fields for child nodes. It works with strings. Its design can be adapted to other value types. The nodes can be optimized with other representations.