Leetcode 720. the longest word in the dictionary

Title Description

720. The longest word in the dictionary

solution ： The meter

Let's put the words Sort by word length , Those with the same length shall be sorted according to the requirements of the topic and the order of the dictionary , Final words It can ensure that every step in the traversal process is the longest at present 、 The word with the smallest dictionary order

If the word currently traversed is deleted, the last letter can be found in the table , Then it shows that the current word meets the requirements of the answer , Then you can update the answer , Insert it into the table

class Solution {
    
public:
    string longestWord(vector<string>& words) {
    
        sort(words.begin(), words.end(), [](const string& a, const string& b){
    
            return a.size() != b.size() ? a.size() < b.size() : a>b;
        });
        string ans;
        unordered_set<string> candidates = {
    ""};
        for (auto word: words)
        {
    
            if (candidates.count(word.substr(0, word.size() - 1)))
            {
    
                candidates.emplace(word);
                ans = word;
            }
        }
        return ans;
    }
};

Solution 2 ： Dictionary tree

This problem is modified on the basis of the dictionary tree search You can get ： At the beginning , We will all word Insert into the dictionary tree , Then the prefix node of each candidate answer that meets the requirements of the question must meet isEnd = true, Next, compare the length and dictionary order to get the longest word

class Trie {
    
private:
    bool isEnd;
    Trie* next[26];

public:
    /** Initialize your data structure here. */
    Trie() {
    
        isEnd = false;
        memset(next, 0, sizeof(next));
    }
    
    /** Inserts a word into the trie. */
    void insert(string word) {
    
        Trie* node = this;
        for(auto c: word)
        {
    
            if(node->next[c-'a']==NULL) node->next[c-'a'] = new Trie();
            node  = node->next[c-'a'];
        }
        node->isEnd = true;
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
    
        Trie* node = this;
        for(auto c: word)
        {
    
            node = node->next[c-'a'];
            if(node==NULL || !node->isEnd) return false;
        }
        return node->isEnd;
    }
};


class Solution {
    
public:
    string longestWord(vector<string>& words) {
    
        Trie trie;
        for (auto word: words) trie.insert(word);
        string ans = "";
        for (auto word: words)
        {
    
            if(trie.search(word))
                if (word.size() > ans.size() || (word.size() == ans.size() && word <ans))
                    ans = word;
        }
        return ans;
    }
};