720.词典中最长的单词

链接：720.词典中最长的单词
难度：Medium
标签：字典树、数组、哈希表、字符串、排序
简介：给出一个字符串数组 words 组成的一本英语词典。返回 words 中最长的一个单词，该单词是由 words 词典中其他单词逐步添加一个字母组成。

题解 1 - cpp

• 编辑时间：2022-03-16
• 执行用时：36ms
• 内存消耗：16.7MB
• 编程语言：cpp
• 解法介绍：排序后遍历。

bool comp(string &a, string &b) {
    return a.size() == b.size() ? a < b : a.size() > b.size();
}
class Solution {
   public:
    string longestWord(vector<string> &words) {
        unordered_set<string> s;
        for (auto &w : words) s.insert(w);
        sort(words.begin(), words.end(), comp);
        for (auto &w : words) {
            if (find(s, w)) return w;
        }
        return "";
    }
    bool find(unordered_set<string> &s, string w) {
        if (w == "") return true;
        if (!s.count(w)) return false;
        return find(s, w.substr(0, w.size() - 1));
    }
};