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%的用户