Longest Word Built Letter by Letter

Return the longest word in words such that every prefix of it (w[:1], w[:2], ..., and the word itself) is also in words. If several are longest, return the smallest in dictionary order. If there is none, return "".

For ["w", "wo", "wor", "worl", "world"] the answer is "world"; for ["a", "banana", "app", "appl", "ap", "apply", "apple"] it is "apple".

Examples

Example 1

Input:

longest_word(['w', 'wo', 'wor', 'worl', 'world'])

Output:

'world'

Example 2

Input:

longest_word(['a', 'banana', 'app', 'appl', 'ap', 'apply', 'apple'])

Output:

'apple'

Constraints

• 0 <= len(words) <= 30000
• 1 <= length <= 30, lower-case letters.