720. 词典中最长的单词

题 目 描 述 color{Violet}题目描述 题目描述

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

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

∙ ullet ∙示例 1：

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

∙ ullet ∙示例 2：

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

链 接 ： [ h t t p s : / / l e e t c o d e − c n . c o m / p r o b l e m s / l o n g e s t − w o r d − i n − d i c t i o n a r y ] color{Brown}链接：[https://leetcode-cn.com/problems/longest-word-in-dictionary] 链接：[https://leetcode−cn.com/problems/longest−word−in−dictionary]

解 题 思 路 color{Violet}解题思路 解题思路

∙ ullet ∙ 整体思路：为了找到最长的符合条件的字符串，我们需要从一个字符开始查看，找到具有最长的公共前缀的其他字符即可。

∙ ullet ∙ 第一步：将words数组排序，按照字符个数从小到大排序，当字符个数相同时根据字典序列排序。在这里我使用了vector数组的sort自定义排序。

∙ ullet ∙ 第二步：对于单个字符的初始情况可以先放入set集合中，然后按顺序从前到后查看是否具有相同的前缀，如果在set中存在则将其放入set中，然后更新最长字符串。

C + + 源 代 码 color{Violet}C++源代码 C++源代码

class Solution {
          
   
public:
    string longestWord(vector<string>& words) {
          
   
        string res="";
        unordered_set<string>set;
        //为word排序
        sort(words.begin(),words.end(),[&](const string&a,const string&b)->bool
        {
          
   
            return a.size()==b.size()?a<b:a.size()<b.size();
        });
        //依次查找具有公共前缀的字符串
        for(string &word:words)
        {
          
   
            if(word.size()==1 || set.count(word.substr(0,word.size()-1)))
            {
          
   
                res=word.size()>res.size()?word:res;
                set.insert(word);
            }
        }
        return res;
    }
};