All problems

Longest Word in Dictionary

Medium · trie

You are given a list of lowercase words words. A word is buildable if it can be made one letter at a time, where every step is also a word in the list: the word itself is in the list, and so is each of its shorter prefixes (its first letter, its first two letters, and so on, up to the whole word).

For example, "tap" is buildable when the list contains "t", "ta" and "tap". If "ta" is missing, "tap" is not buildable, even though "t" and "tap" are present.

Return the longest buildable word. If several buildable words share the longest length, return the one that comes first in alphabetical (dictionary) order. If no word is buildable, return the empty string "".

The list may contain the same word more than once.

Examples

Example 1

Input: words = ["t", "ta", "tap", "tape", "tar", "taro", "tarot", "to"]

Output: "tarot"

"tarot" is built through "t", "ta", "tar", "taro". "tape" is shorter, with only four letters.

Example 2

Input: words = ["m", "mo", "mop", "ma", "map", "mat", "x"]

Output: "map"

"map", "mat" and "mop" are all buildable and have three letters. "map" comes first alphabetically.

Example 3

Input: words = ["bat", "ba", "cat"]

Output: ""

There is no one-letter word to start from, so nothing can be built.

Constraints