# 720.Longest Word in Dictionary

**720.Longest Word in Dictionary**

难度:Easy

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

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

```
示例 1:

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

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

所有输入的字符串都只包含小写字母。
words数组长度范围为[1,1000]。
words[i]的长度范围为[1,30]。
```

可以先按照所需要的順序，即字符串長度進行排序，然後從前往後判斷是否是有效字符串。\
由於前面的肯定比後面的長，因此在前面判斷的時候，可以借鑑斐波那契數列的方法，用一個set將中間結果存起來，後面的可以直接查詢該set。

```
class Solution {
unordered_set<string>isChecked;
bool isValid(string s, unordered_set<string>word)
{
    if(isChecked.count(s)) return true;
    string res;
    for(auto c:s)
    {
        res+=c;
        if(!word.count(res)) return false;
        else isChecked.insert(res);
    }
    return true;
    
}
public:
    string longestWord(vector<string>& words) {
        int len=0;
        unordered_set<string>word(words.begin(),words.end());
        sort(words.begin(), words.end(), [](string a,string b){if(a.length() > b.length()) return true; else if(a.length() == b.length() && a<b) return true; else return false;});
        for(auto w: words)
        {
            if(isValid(w,word)) 
            {
                return w;
            }
        }
        
        return "";
        
        
        
        
    }
};
```

> 执行用时 :264 ms, 在所有 C++ 提交中击败了15.95%的用户\
> 内存消耗 :63.2 MB, 在所有 C++ 提交中击败了5.88%的用户


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://dfine.gitbook.io/leetcode/720.longest_word_in_dictionary.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.