Shortest Unique Prefix


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]


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.

Online Judge