Skip to content

Instantly share code, notes, and snippets.

@benyblack
Last active April 13, 2017 13:18
Show Gist options
  • Save benyblack/23cfeda6772b3d54c69139d4d2064604 to your computer and use it in GitHub Desktop.
Save benyblack/23cfeda6772b3d54c69139d4d2064604 to your computer and use it in GitHub Desktop.
Trie structure in c#
using System;
using System.Collections.Generic;
using System.Linq;
namespace MyTrie {
public class TrieNode {
Dictionary<char, TrieNode> children = new Dictionary<char, TrieNode>();
public int Size { get; set; }
public TrieNode() {
Size = 0;
}
private TrieNode GetNode(char c) {
if (children.ContainsKey(c)) {
return children[c];
}
return null;
}
private void SetNode(char c, TrieNode node) {
if (!children.ContainsKey(c)) {
children.Add(c, node);
}
}
public bool Search(string word) {
return Search(word, 0);
}
public bool Search(string s, int index) {
if (index == s.Length) {
return true;
}
TrieNode child = GetNode(s[index]);
if (child == null) {
return false;
}
return child.Search(s, index + 1);
}
public void Add(string s) {
Add(s, 0);
}
private void Add(string s, int index) {
Size++;
if (s.Length == index) return;
char current = s[index];
TrieNode child = GetNode(current);
if (child == null) {
child = new TrieNode();
SetNode(current, child);
}
child.Add(s, index + 1);
}
public int FindCount(string s, int index) {
if (index == s.Length) {
return Size;
}
TrieNode child = GetNode(s[index]);
if (child == null) {
return 0;
}
return child.FindCount(s, index + 1);
}
public List<string> Find(string s, int index) {
if (index == s.Length) {
return GetChildWords();
}
TrieNode child = GetNode(s[index]);
if (child == null) {
return null;
}
return child.Find(s, index + 1);
}
public List<string> GetChildWords() {
List<string> l = new List<string>();
foreach (var child in children) {
if (l.Count > 0 && l[l.Count - 1] == "") {
l[l.Count - 1] = child.Key.ToString();
} else {
l.Add(child.Key.ToString());
}
child.Value.GetChildWords(ref l);
}
if (l.Count > 0 && l[l.Count - 1] == "") {
l.RemoveAt(l.Count - 1);
}
return l;
}
public void GetChildWords(ref List<string> l) {
foreach (var child in children) {
l[l.Count - 1] += child.Key;
if (child.Value.children.Count == 0) {
l.Add("");
return;
}
child.Value.GetChildWords(ref l);
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment