Shortest Unique Prefix

Problem

Use the shortest unique prefix to represent each word in the array

• input: ["zebra", "dog", "duck", "dot"]
• output: {zebra: z, dog: dog, duck: du, dot:dot}

If it is just a prefix, not the full word, return empty string.

[bearcat, bear]
{bearcat: bearc, bear: ""}

[ab, abb, abbb]
{abbb:abbb;abb:"";ab:""}

Solution

Use a trie (a.k.a. a prefix tree), for every char in the word increase the count of the corresponding node by one. Then for every word, find the first node that has the count of value 1.