problem
720. Longest Word in Dictionary
题意:
solution1: BFS;
class Solution {
public:
string longestWord(vector<string>& words) {
string res = "";
unordered_set<string> s(words.begin(), words.end());
queue<string> q;
for(auto word:words)
{
if(word.size()==) q.push(word);
}
int maxLen = ;
while(!q.empty())
{
string t = q.front();
q.pop();
if(t.size()>maxLen)
{
maxLen = t.size();
res = t;//err....
}
else if(t.size()==maxLen) res = min(res, t);
for(char ch='a'; ch<='z'; ++ch)//err...
{
t.push_back(ch);
if(s.count(t)) q.push(t);
t.pop_back();
}
}
return res;
}
};
solution2:
class Solution {
public:
string longestWord(vector<string>& words) {
string res = "";
unordered_set<string> s(words.begin(), words.end());
int maxLen = ;
for (auto word:words)
{
if(word.size()==) helper(s, word, maxLen, res);
}
return res;
}
void helper(unordered_set<string>& s, string word, int& maxLen, string& res) {
if(word.size()>maxLen)
{
maxLen = word.size();
res = word;
}
else if(word.size()==maxLen) res = min(res, word);
for(char ch = 'a'; ch<='z'; ++ch)
{
word.push_back(ch);
if(s.count(word)) helper(s, word, maxLen, res);
word.pop_back();
}
}
};
参考
1. Leetcode_easy_720. Longest Word in Dictionary;
2. Grandyang;
完