Longest Prefix

Problem statement

Given a list of string words, find the longest string in words such that every prefix of that string is also present in words. If there is more than one string with the same length, return any valid string; if none exists, return -1 as string.

Example 1

Sample input

Sample output

Explanation

The word "games" has prefixes "game", "gam", "ga", and "g", and all of them appear in words.

Example 2

Sample Input

Sample output

Explanation

Both "apple" and "apply" have all their prefixes in words list. However, "apple" is lexicographically smaller, so we return "apple".

Example 3

Sample input

Sample output

Explanation

None of the given string has their every prefix present in words. So, -1 is returned.

Try it yourself

Try to solve the following problem yourself before reading the solution.

Intuition

Let's try to understand this problem by taking the example of the word games. 

The prefixes of the word games are g, ga, gam, game, and games. 

To insert these prefixes into the trie, a new node is appended to the already existing path in the trie at each step. When we insert ga, we only add a new node for a since g already exists. When we insert gam, we add only a new node for m since ga already exists. Similarly, for game, we add a new node for e since the path for gam already exists in the trie.

The above details help us in building intuition for solving this problem. When inserting a new word in the trie, if we only need to add a single node to an already existing path, it means that all the valid prefixes of that word are already present in the trie and therefore in the words list.

Algorithm

The summary of the algorithm is given below.

Step 1: Sorting the word list

For the insert function to work as intended, it's necessary to sort the words according to their size so that the smaller words get inserted into the trie first. ...