720.Longest Word in Dictionary
720.Longest Word in Dictionary
难度:Easy
给出一个字符串数组words组成的一本英语词典。从中找出最长的一个单词,该单词是由words词典中其他单词逐步添加一个字母组成。若其中有多个可行的答案,则返回答案中字典序最小的单词。
若无答案,则返回空字符串。
1
示例 1:
2
3
输入:
4
words = ["w","wo","wor","worl", "world"]
5
输出: "world"
6
解释:
7
单词"world"可由"w", "wo", "wor", 和 "worl"添加一个字母组成。
8
示例 2:
9
10
输入:
11
words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
12
输出: "apple"
13
解释:
14
"apply"和"apple"都能由词典中的单词组成。但是"apple"得字典序小于"apply"。
15
注意:
16
17
所有输入的字符串都只包含小写字母。
18
words数组长度范围为[1,1000]。
19
words[i]的长度范围为[1,30]。
Copied!
可以先按照所需要的順序,即字符串長度進行排序,然後從前往後判斷是否是有效字符串。 由於前面的肯定比後面的長,因此在前面判斷的時候,可以借鑑斐波那契數列的方法,用一個set將中間結果存起來,後面的可以直接查詢該set。
1
class Solution {
2
unordered_set<string>isChecked;
3
bool isValid(string s, unordered_set<string>word)
4
{
5
if(isChecked.count(s)) return true;
6
string res;
7
for(auto c:s)
8
{
9
res+=c;
10
if(!word.count(res)) return false;
11
else isChecked.insert(res);
12
}
13
return true;
14
15
}
16
public:
17
string longestWord(vector<string>& words) {
18
int len=0;
19
unordered_set<string>word(words.begin(),words.end());
20
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;});
21
for(auto w: words)
22
{
23
if(isValid(w,word))
24
{
25
return w;
26
}
27
}
28
29
return "";
30
31
32
33
34
}
35
};
Copied!
执行用时 :264 ms, 在所有 C++ 提交中击败了15.95%的用户 内存消耗 :63.2 MB, 在所有 C++ 提交中击败了5.88%的用户
Copy link