720. Longest Word in Dictionary

• Difficulty: Easy

• Topics: Hash Table, Trie

• Similar Questions:

  • Longest Word in Dictionary through Deleting

  • Implement Magic Dictionary

Problem:

Given a list 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.

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".

Note:

Solutions:

class Solution {
public:
    string longestWord(vector<string>& words) {
        auto comparator = [](const string& word1, const string& word2) {
            if (word1.length() != word2.length()) {
                return word1.length() < word2.length();
            }  
            return word1 > word2;
        };

        sort(words.begin(), words.end(), comparator);
        unordered_set<string> cache;
        string ret;
        for (int i = 0; i < words.size(); ++i) {
            if (words[i].length() <= 1) {
                ret = words[i];
                cache.insert(words[i]);
                continue;
            }

            string prefix = words[i].substr(0, words[i].length() - 1);
            if (cache.count(prefix)) {
                ret = words[i];
                cache.insert(words[i]);
            }
        }

        return ret;

    }
};