题目描述 [词典中最长的单词]

给出一个字符串数组words组成的一本英语词典。从中找出最长的一个单词，该单词是由words词典中其他单词逐步添加一个字母组成。若其中有多个可行的答案，则返回答案中字典序最小的单词。

若无答案，则返回空字符串。

示例

输入:
words = ["w","wo","wor","worl", "world"]
输出: "world"
解释:
单词"world"可由"w", "wo", "wor", 和 "worl"添加一个字母组成。

解题思路

注意：如果这个有ab,abc，那么是不可以的，因为没有a，也就是说必须最长字母的每一个非空子串都在words里面。一开始没搞懂这个意思。

• 先对words进行排序
• 可以用一个hashset保存字符串（首先加入一个空串，便于长度为1的字符串和大于1的字符串同等处理），如果能找到这个字符串的子串（除去末尾最后一个字符），则将该字符串加入set;
• 同时保存最长字符串，如果字符串长度相等，则返回字典序小的那个
  这题还可以用字典树实现，不过其实没必要。哈哈哈哈，代码见下面。

代码

class Solution {
public:
    string longestWord(vector<string>& words) {
        unordered_set<string> hashset;
        string max_word = "";
        if(words.size()==0) return max_word;
        sort(words.begin(), words.end());
        hashset.insert("");
        for(int i=0;i<words.size();i++){
            string word = words[i];
            word.erase(word.size()-1);
            if(hashset.count(word)>0){
                hashset.insert(words[i]);
                if(words[i].size()>max_word.size()) max_word = words[i];
                else if(words[i].size()==max_word.size())
                    max_word = max_word<words[i] ? max_word : words[i];
            }
        }
        return max_word;
    }
};

字典树实现

class Solution {
public:
    int k=1;
    int flag[1001];
    int trie[1001][26];
    void insert(string s){
        int p=0;
        for(int i=0;i<s.size();i++){
            int c = s[i] - 'a';
            if(!trie[p][c]){
                trie[p][c] = k;
                k++;
            }
            p = trie[p][c];
        }
        flag[p] = 1;
    }

    int serach(string s){
        int p=0;
        for(int i=0;i<s.size();i++){
            int c = s[i] - 'a';
            if(!trie[p][c]) return 0;
            p = trie[p][c];
        }
        return flag[p]==1;
    }

    string longestWord(vector<string>& words) {
        sort(words.begin(), words.end());
        string max_word="";
        for(auto word:words){
            if(serach(word.substr(0, word.size()-1))||word.size()==1){
                insert(word);
                if(word.size()>max_word.size()) max_word = word;
                else if(word.size()==max_word.size())
                    max_word = max_word<word ? max_word : word;
            }
        }
        return max_word;
    }
};