All problems

Shortest Locker Stickers

Medium · trie

A gym has one locker for each member, and each locker must carry a small sticker showing the beginning of the member's name. You are given the list names of the members' names: all different, each made of lowercase letters.

A sticker is good for a name when it is a start of that name (a prefix, possibly the whole name) and no other name in the list starts with it. Give every member the shortest good sticker.

Sometimes no start is good, because every start of a name, even the whole name, is also the start of another longer name. Then the sticker is the whole name.

Return a list with one sticker per name, in the same order as names.

Examples

Example 1

Input: names = ["dog", "dove", "duck"]

Output: ["dog", "dov", "du"]

"d" is shared by all three. "do" is shared by "dog" and "dove". "dog" and "dov" are used by one name each, and "du" only by "duck".

Example 2

Input: names = ["car", "cart", "cat"]

Output: ["car", "cart", "cat"]

"car" is also the start of "cart", so every start of "car" is shared and the whole name is used. "cart" needs all four letters to leave "car" behind, and "cat" needs three letters.

Example 3

Input: names = ["solo"]

Output: ["s"]

With nobody else, one letter is enough.

Constraints