今天的每日一题！LeetCode 720. 词典中最长的单词,想了很久，功夫还是不到家啊。

题目

给出一个字符串数组 words 组成的一本英语词典。返回 words 中最长的一个单词，该单词是由 words 词典中其他单词逐步添加一个字母组成。

若其中有多个可行的答案，则返回答案中字典序最小的单词。若无答案，则返回空字符串。

示例

示例1：

1
2
3

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

示例2：

1
2
3

输入：words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
输出："apple"
解释："apply" 和 "apple" 都能由词典中的单词组成。但是 "apple" 的字典序小于 "apply"

题解

很简单一个东西，结果给我想复杂了。
阅读题目，作为一个words中最长的一个字符串，它由words中其他单词逐步添加一个字母形成，那么这个字符串 word 的 word.substr(0,word.size()-1)) 必定存在。

以示例一为例，“world”.substr(0,"world".size()-1) = "worl", 而 “worl”.substr(0,"worl".size()-1) = "wor",很好理解，我们就是要找这种类型的最长的字符串，所以我们只要检索这个字符串的substr(0,word.size()-1))是否存在于words中即可，如果这个字符串的所有“前导”全都存在，就记录进ans中。

代码

我写的代码

//执行 1260ms 超越5.26%   内存 25.2 MB 超越 45.15%
class Solution {
public:

    string longestWord(vector<string>& words) {
        sort(words.begin(),words.end(),[](const string & a,const string & b){
            if(a.size()!=b.size())
                return a.size()>b.size();
            return a>b;
        }); //从大到小排序，字典序靠前的向后移
        string ans;
        for(auto i:words)
        {
            bool bl=true;
            cout<<i<<endl;
            if(ans.size()>i.size()) //当ans长度超过当前遍历到的字符串的长度后直接退出
                break;
            for(int j=i.size()-1;j>0;j--) //蠢蛋写法，每一个字符串都要再次从头开始遍历查询，消耗大量时间
            {
                if(find(words.begin(),words.end(),i.substr(0,j))==words.end()) 
                {
                    bl=false;
                    break;
                }

            }
            if(bl)
                ans=i;
        }
        return ans;
    }
};

写完后其实不满意，耗时太高，于是看了官方的代码。笨蛋如我，居然没想到用 set 容器，按照官方做法可以节省下一大笔的时间花费和空间花费。

官方做法

class Solution {
public:
    string longestWord(vector<string>& words) {
        sort(words.begin(), words.end(), [](const string & a, const string & b) {
            if (a.size() != b.size()) 
            {
                return a.size() < b.size();
            } 
            else 
            {
                return a > b;
            }
        });  //从小到大排序，字典序靠前的向后移
        string ans = "";
        set<string> cnt;
        cnt.emplace("");
        for (auto word : words) 
        {
            if (cnt.count(word.substr(0, word.size() - 1))) { //当查到“前导”字符串即添加进set容器并保存进ans
                cnt.emplace(word);
                ans = word;
            }
        }
        return longest;
    }
};