Last active
April 13, 2017 13:18
-
-
Save benyblack/23cfeda6772b3d54c69139d4d2064604 to your computer and use it in GitHub Desktop.
Trie structure in c#
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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