using System;

using System.Text;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        Trie t = new Trie();

        t.Insert("dog");

        t.Insert("dogs");

        t.Insert("house");

        t.Insert("test");

        t.Insert("housewarming");

        Console.WriteLine(t.findUniquePrefix("dog"));

        Console.WriteLine(t.findUniquePrefix("dogs"));

        Console.WriteLine(t.findUniquePrefix("housewarming"));

    }

    public class Trie {

        public TrieNode root = new TrieNode('\0');

        public void Insert(string s) {

            TrieNode curr = root;

            for(int i = 0; i < s.Length; i++) {

                curr.wordCount++;

                char c = s[i];

                if (!curr.children.ContainsKey(c)) {

                    curr.children.Add(c, new TrieNode(c));  

                }

                curr = curr.children[c];                

            }

            curr.wordCount++;

            curr.isWord = true;

        }

        public string findUniquePrefix(string s) {

            Dictionary<char, TrieNode> children = root.children;

            StringBuilder str = new StringBuilder();

            for(int i = 0; i < s.Length; i++) {

                char c = s[i];

                str.Append(c);

                TrieNode curr = children[c];

                //Console.WriteLine(curr);

                if (curr.wordCount == 1) {

                    return str.ToString();

                }               

                if (curr.isWord && string.Equals(str.ToString(), s)) {

                    return str.ToString();

                }

                children = curr.children;               

            }

            return string.Empty;

        }

    }

    public class TrieNode {

        public char val;

        public bool isWord;

        public int wordCount;

        public Dictionary<char, TrieNode> children;

        public TrieNode(char val) {

            this.val = val;

            this.wordCount = 0;

            children = new Dictionary<char, TrieNode>();

        }

        public override string ToString() {

            return string.Format("{0} is word: {1} count {2}", val, isWord, wordCount); 

        }

    }

}