You are given a list of strings. You need to find the shortest unique prefix for each string.

Problem Note:

  • The shortest unique prefix of a string is the prefix of that string such that no other string in the list has that prefix.
  • Assume that no word is prefix of another.
  • All prefixes need not be of same length
  • The expected time complexity is O(nlogn) or better.
Example 1
Input: {"alphabet", "carpet", "cartoon", "carrot", "alpine"}
Output: {"alph", "carp", "cart", "carr", "alpi"}

Example 2
Input: {"create", "big"}
Output: {"c", "b"}