Comment on page
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%的用户
Last modified 1yr ago