Given an array of strings words representing an English Dictionary, return 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 the empty string.

Note that the word should be built from left to right with each additional character being added to the end of a previous word.

Example 1:

Input: words = ["w","wo","wor","worl","world"]
Output: "world"
Explanation: The word "world" can be built one character at a time by "w", "wo", "wor", and "worl".

Example 2:

Input: words = ["a","banana","app","appl","ap","apply","apple"]
Output: "apple"
Explanation: Both "apply" and "apple" can be built from other words in the dictionary. However, "apple" is lexicographically smaller than "apply".

Constraints:

• $1 \leq$ words.length $\leq 1000$
• $1 \leq$ words[i].length $\leq 30$
• words[i] consists of lowercase English letters.

Brute Force

For this problem, we're asked to find the longest word with smallest lexicographical order such that all its non-empty prefixes exist in words. Let's call a word good if all its prefixes exist in words. We can verify if this is the case by iterating through all prefixes to check if they all exist. Let's denote $L$ as the length of the longest good word. Out of all good words with length $L$, we'll return the one with lexicographically least length.

Full Solution

Let's denote $x_i$ as the length of words[i].

We can observe that words[i] is good if $x_i = 1$ or the prefix of words[i] with length $x_i - 1$ is good.

Let's try to find a way to use this idea to process all words efficiently. Since processing a word with length $x_i$ requires a word with length $x_i - 1$ to be processed, we should process words by non-decreasing length. This can be done by sorting and simply iterating through the sorted list. In addition, we'll use a hashmap to act as a lookup table for good words.

In our algorithm, we'll iterate through words by non-decreasing length. For each word, we'll check if it's good with the method mentioned above. If the word is good, we'll update it in our hashmap.

Time Complexity

Let's denote $N$ as the length of words and $S$ as the sum of lengths of all words in words.

Since sorting takes $\mathcal{O}(N\log{N})$ and our main algorithm takes $\mathcal{O}(S)$ from comparing keys, our final time complexity is $\mathcal{O}(N\log{N}+S)$.

Time Complexity: $\mathcal{O}(N\log{N}+S)$

Space Complexity

Since our hashmap has $\mathcal{O}(N)$ memory, our space complexity is $\mathcal{O}(N)$.

Space Complexity: $\mathcal{O}(N)$

C++ Solution

1class Solution {
2   public:
3    static bool comp(string s, string t) {  // sorting comparator
4        return s.size() < t.size();
5    }
6    string longestWord(vector<string>& words) {
7        sort(words.begin(), words.end(), comp);  // sort words by non-decreasing length
8        unordered_map<string, bool> goodWords;        // lookup for good words
9        int maxLength = 0;
10        string ans = "";
11        for (string word : words) {
12            if (word.size() == 1) {
13                goodWords[word] = true;
14            } else if (goodWords[word.substr(0, word.size() - 1)]) {  // word with length - 1 prefix is good
15                goodWords[word] = true;
16            }
17            if (goodWords[word]) {
18                if (maxLength < word.size()) {  // find longer word
19                    maxLength = word.size();
20                    ans = word;
21                } else if (maxLength == word.size()) {  // find lexicographically smaller word
22                    ans = min(ans, word);
23                }
24            }
25        }
26        return ans;
27    }
28};

Java Solution

1class Solution {
2    public String longestWord(String[] words) {
3        Arrays.sort(words, (a, b) -> a.length() - b.length()); // sort words by non-decreasing length
4        HashMap<String, Boolean> goodWords = new HashMap(); // lookup for good words
5        int maxLength = 0;
6        String ans = "";
7        for (String word : words) {
8            if (word.length() == 1) {
9                goodWords.put(word, true);
10            } else if (goodWords.containsKey(word.substring(0, word.length() - 1))) {
11                // word with length - 1 prefix is good
12                goodWords.put(word, true);
13            }
14            if (goodWords.containsKey(word)) {
15                if (maxLength < word.length()) { // find longer word
16                    maxLength = word.length();
17                    ans = word;
18                } else if (maxLength == word.length()
19                    && ans.compareTo(word) > 0) { // find lexicographically smaller word
20                    ans = word;
21                }
22            }
23        }
24        return ans;
25    }
26}

Python Solution

Note: A set can be used in python which acts as a hashset and serves the same purpose as a hashmap in this solution.

1class Solution:
2    def longestWord(self, words: List[str]) -> str:
3        words.sort(key=len)  # sort words by non-decreasing length
4        goodWords = set()  # lookup for good words
5        maxLength = 0
6        ans = ""
7        for word in words:
8            if len(word) == 1:
9                goodWords.add(word)
10            elif word[:-1] in goodWords:  # word with length - 1 prefix is good
11                goodWords.add(word)
12            if word in goodWords:
13                if maxLength < len(word):  # find longer word
14                    maxLength = len(word)
15                    ans = word
16                elif maxLength == len(word):  # find lexicographically smaller word
17                    ans = min(ans, word)
18        return ans
19