929. Longest Word in Dictionary (Trie)

Given a list of words, return the longest word that can be built one character at a time, where every prefix of it (of every shorter length) is also present in the list. If several qualify, return the lexicographically smallest. If none qualifies, return an empty string. The input is a JSON array of words.

Input: A JSON array of words.

Output: Quoted string — the longest buildable word.

Examples

Input: ["w","wo","wor","worl","world"]
Output: "world"
Explanation: Every prefix exists.

Input: ["a","banana","app","appl","ap","apply","apple"]
Output: "apple"
Explanation: 'apple' is buildable and smallest among ties.

Input: ["x"]
Output: "x"
Explanation: Single word.

Constraints

• 1<=words<=10^4
• lowercase letters

Asked by