Skip to content

Instantly share code, notes, and snippets.

@efruchter
Last active April 22, 2018 21:35
Show Gist options
  • Save efruchter/c699a75420363c95b1ad to your computer and use it in GitHub Desktop.
Save efruchter/c699a75420363c95b1ad to your computer and use it in GitHub Desktop.
A Trie implementation in C#
using System;
using System.Collections.Generic;
/**
* A space-saving data structure to store words and their counts.
* Words that share prefixes will have common paths along a branch of the tree.
*/
public class Trie
{
private TrieNode head;
public Trie ()
{
head = new TrieNode();
}
/**
* Add a word to the trie.
* Adding is O (|A| * |W|), where A is the alphabet and W is the word being searched.
*/
public void AddWord(string word)
{
TrieNode curr = head;
curr = curr.GetChild (word [0], true);
for (int i = 1; i < word.Length; i++)
{
curr = curr.GetChild (word [i], true);
}
curr.AddCount ();
}
/**
* Get the count of a partictlar word.
* Retrieval is O (|A| * |W|), where A is the alphabet and W is the word being searched.
*/
public int GetCount(string word)
{
TrieNode curr = head;
foreach (char c in word)
{
curr = curr.GetChild (c);
if (curr == null)
{
return 0;
}
}
return curr.count;
}
internal class TrieNode
{
private LinkedList<TrieNode> children;
public int count { private set; get; }
public char data { private set; get; }
public TrieNode(char data = ' ')
{
this.data = data;
count = 0;
children = new LinkedList<TrieNode>();
}
public TrieNode GetChild(char c, bool createIfNotExist = false)
{
foreach (var child in children)
{
if (child.data == c)
{
return child;
}
}
if (createIfNotExist)
{
return CreateChild (c);
}
return null;
}
public void AddCount()
{
count++;
}
public TrieNode CreateChild(char c)
{
var child = new TrieNode (c);
children.AddLast (child);
return child;
}
}
}
@hadeer1996
Copy link

I have a file and do not need to search for some of the data in this file, for example, I want to search for all the words that are related to the word hello in that the file . how i can do this search with trie?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment