using System.Collections.Generic;
public static void Main()
t.Insert("housewarming");
Console.WriteLine(t.findUniquePrefix("dog"));
Console.WriteLine(t.findUniquePrefix("dogs"));
Console.WriteLine(t.findUniquePrefix("housewarming"));
public TrieNode root = new TrieNode('\0');
public void Insert(string s) {
for(int i = 0; i < s.Length; i++) {
if (!curr.children.ContainsKey(c)) {
curr.children.Add(c, new TrieNode(c));
public string findUniquePrefix(string s) {
Dictionary<char, TrieNode> children = root.children;
StringBuilder str = new StringBuilder();
for(int i = 0; i < s.Length; i++) {
TrieNode curr = children[c];
if (curr.wordCount == 1) {
if (curr.isWord && string.Equals(str.ToString(), s)) {
children = curr.children;
public Dictionary<char, TrieNode> children;
public TrieNode(char val) {
children = new Dictionary<char, TrieNode>();
public override string ToString() {
return string.Format("{0} is word: {1} count {2}", val, isWord, wordCount);