Find shortest unique prefix for every word in a given list - GeeksforGeeks

Find shortest unique prefix for every word in a given list - GeeksforGeeks

Find shortest unique prefix for every word in a given list

Given an array of words, find all shortest unique prefixes to represent each word in the given array. Assume that no word is prefix of another.

Examples:

Input: arr[] = {"zebra", "dog", "duck", "dove"}  Output: dog, dov, du, z  Explanation: dog => dog               dove = dov                duck = du               z   => zebra     Input: arr[] =  {"geeksgeeks", "geeksquiz", "geeksforgeeks"};  Output: geeksf, geeksg, geeksq}  

We strongly recommend you to minimize your browser and try this yourself first.

A Simple Solution is to consider every prefix of every word (starting from the shortest to largest), and if a prefix is not prefix of any other string, then print it.

An Efficient Solution is to use Trie. The idea is to maintain a count in every node. Below are steps.

1) Construct a Trie of all words. Also maintain frequency of every node (Here frequency is number of times node is visited during insertion). Time complexity of this step is O(N) where N is total number of characters in all words.

2) Now, for every word, we find the character nearest to the root with frequency as 1. The prefix of the word is path from root to this character. To do this, we can traverse Trie starting from root. For every node being traversed, we check its frequency. If frequency is one, we print all characters from root to this node and don't traverse down this node.

Time complexity if this step also is O(N) where N is total number of characters in all words.

Read full article from Find shortest unique prefix for every word in a given list - GeeksforGeeks