Given a list of strings words
representing an English Dictionary, find the longest word in words
that can be built one character at a time by other words in words
. If there is more than one possible answer, return the longest word with the smallest lexicographical order.
Example 1:
Input: words = ["w","wo","wor","worl", "world"] Output: "world" Explanation: The word "world" can be built one character at a time by "w", "wo", "wor", and "worl".
Example 2:
Input: words = ["a", "banana", "app", "appl", "ap", "apply", "apple"] Output: "apple" Explanation: Both "apply" and "apple" can be built from other words in the dictionary. However, "apple" is lexicographically smaller than "apply".
Note:
words
will be in the range [1, 1000]
.words[i]
will be in the range [1, 30]
.A:
class Solution { public: string longestWord(vector<string>& words) { unordered_set<string> set(words.begin(), words.end()); string res = ""; vector<string> preLayer; preLayer.push_back(res); while(preLayer.size()>0){ res = preLayer[0]; vector<string> curLayer; for(auto str:preLayer){ for(char ch = 'a'; ch<='z'; ++ch){ string ss = str+ch; if(set.find(ss) != set.end()){ curLayer.push_back(ss); } } } preLayer = curLayer; } return res; } };
错误在:
2个for loop 次序颠倒了。 哎, 肏
No comments:
Post a Comment