Shortest Unique Prefixes, by Square

Here is the problem, powered by Daily Coding Problem:

This problem was asked by Square.

Given a list of words, return the shortest unique prefix of each word. For example, given the list:

• dog
• cat
• apple
• apricot
• fish

Return the list:

• d
• c
• app
• apr
• f

The solution can be done in linear time by using a Trie using the following strategy:

1. Create a trie using Hash Tables but each element has a count of how many times it has been seen
2. Add all the words to the trie
3. When you're done, parse the trie looking for the nodes that have count equals to 1. It means that it is a unique prefix. Print it

Code is below and also on Github, right here: https://github.com/BorisVasilenko/dailycodingproblem/blob/master/DailyCodingProblem02232019.cs. Cheers, ACC.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Collections;

namespace DailyCodingProblem
{
 class DailyCodingProblem02232019
 {
  public void MinUniquePrefix()
  {
   string[] names = { "dog", "cat", "apple", "apricot", "fish", "Boris", "principal", "micro", "fun", "funny", "mark", "partner" };

   PrefixTrie pTrie = new PrefixTrie();
   foreach (string name in names)
   {
    pTrie.AddWord(name);
   }

   pTrie.PrintMinUniquePrefixes("");
  }
 }

 class PrefixTrie
 {
  public int count = 0;
  private Hashtable children = null;

  public void AddWord(string word)
  {
   if (String.IsNullOrEmpty(word))
   {
    return;
   }
   if (children == null) children = new Hashtable();
   PrefixTrie child = null;
   if (!children.ContainsKey(word[0]))
   {
    child = new PrefixTrie();
    children.Add(word[0], child);
   }
   child = (PrefixTrie)children[word[0]];
   child.count++;
   child.AddWord(word.Substring(1));
  }

  public void PrintMinUniquePrefixes(string prefix)
  {
   if (children == null) return;
   foreach (char c in children.Keys)
   {
    PrefixTrie child = (PrefixTrie)children[c];
    if (child.count == 1)
    {
     Console.WriteLine("{0}", prefix + c.ToString());
    }
    else if (child.count > 1)
    {
     child.PrintMinUniquePrefixes(prefix + c.ToString());
    }
   }
  }
 }

}