C# || How To Implement Trie Prefix Tree Using C#

November 09, 2021 admin No comments

The following is a module with functions which demonstrates how to implement a trie prefix tree using C#.

1. Trie – Problem Statement

A trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

Trie() Initializes the trie object.
void insert(String word) Inserts the string word into the trie.
boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Example 1:

Input ["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]] Output [null, null, true, false, true, null, true]
Explanation Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // return True trie.search("app"); // return False trie.startsWith("app"); // return True trie.insert("app"); trie.search("app"); // return True

2. Trie – Solution

The following is a solution which demonstrates how to implement a trie prefix tree.





		
		
			2. Trie - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 9, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to implement a trie prefix tree
// ============================================================================
// Trie
public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }
    public void Insert(string word) {
        var node = root;
        foreach (var ch in word) {
            if (!node.ContainsKey(ch)) {
                node.Add(ch, new TrieNode());
            }
            node = node.Get(ch);
        }
        node.SetComplete();
    }
    // Search a prefix or whole key in trie and
    // returns the node where search ends
    public TrieNode SearchPrefix(string word) {
        var node = root;
        foreach (var ch in word) {
            if (node.ContainsKey(ch)) {
                node = node.Get(ch);
            } else {
                return null;
            }
        }
        return node;
    }
    public bool Search(string word) {
        var node = SearchPrefix(word);
        return node != null && node.IsComplete();
    }
    public bool StartsWith(string prefix) {
        var node = SearchPrefix(prefix);
        return node != null;
    }
}

// TrieNode
public class TrieNode {
    private Dictionary<char, TrieNode> children;
    private bool isComplete;
    private int count;

    public TrieNode() {
        children = new Dictionary<char, TrieNode>();
    }
    public bool ContainsKey(char ch) {
        return children.ContainsKey(ch);
    }
    public TrieNode Get(char ch) {
        return children[ch];
    }
    public void Add(char ch, TrieNode node) {
        children[ch] = node;
    }
    public void SetComplete() {
        isComplete = true;
        ++count;
    }
    public bool IsComplete() {
        return isComplete;
    }
    public int WordCount() {
        return count;
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 9, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to implement a trie prefix tree
// ============================================================================
// Trie
public class Trie {
    private TrieNode root;
 
    public Trie() {
        root = new TrieNode();
    }
    public void Insert(string word) {
        var node = root;
        foreach (var ch in word) {
            if (!node.ContainsKey(ch)) {
                node.Add(ch, new TrieNode());
            }
            node = node.Get(ch);
        }
        node.SetComplete();
    }
    // Search a prefix or whole key in trie and
    // returns the node where search ends
    public TrieNode SearchPrefix(string word) {
        var node = root;
        foreach (var ch in word) {
            if (node.ContainsKey(ch)) {
                node = node.Get(ch);
            } else {
                return null;
            }
        }
        return node;
    }
    public bool Search(string word) {
        var node = SearchPrefix(word);
        return node != null && node.IsComplete();
    }
    public bool StartsWith(string prefix) {
        var node = SearchPrefix(prefix);
        return node != null;
    }
}
 
// TrieNode
public class TrieNode {
    private Dictionary<char, TrieNode> children;
    private bool isComplete;
    private int count;
 
    public TrieNode() {
        children = new Dictionary<char, TrieNode>();
    }
    public bool ContainsKey(char ch) {
        return children.ContainsKey(ch);
    }
    public TrieNode Get(char ch) {
        return children[ch];
    }
    public void Add(char ch, TrieNode node) {
        children[ch] = node;
    }
    public void SetComplete() {
        isComplete = true;
        ++count;
    }
    public bool IsComplete() {
        return isComplete;
    }
    public int WordCount() {
        return count;
    }
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

[null,null,true,false,true,null,true]

Was this article helpful?

👍 YesNo

Posted in: C#, Console Tags: c-sharp, leetcode, trie

C# || How To Implement Trie Prefix Tree Using C#

Related

Leave a ReplyCancel reply

Search

Compile Your Code Now

Translate Page

Popular Pages

Recent

Archives

Categories