We’re preparing your current view and syncing the latest data.
Given an array of strings words representing an English Dictionary, find the longest word in words that can be built one character at a time by other words in words. If there is more than one possible answer, return the longest word with the smallest lexicographical order. If there is no answer, return an empty string.
Each word in the dictionary consists of lowercase English letters only.
An array of strings words.
A string representing the longest word that meets the condition.
1 <= words.length <= 1000 1 <= words[i].length <= 30 All strings in words consist of lowercase letters.
Example 1
Input
["w","wo","wor","worl","world"]
Output
"world"
Explanation
The word 'world' can be built one character at a time from other words in the dictionary: 'w', 'wo', 'wor', 'worl', 'world'.
Example 2
Input
["a", "banana", "app", "appl", "ap", "apply", "apple"]
Output
"apple"
Explanation
Both 'apply' and 'apple' can be built from other words, but 'apple' is lexicographically smaller.