class Solution {
public:
struct Trie {
Trie() {
end = false;
next.resize(26, nullptr);
}
bool end;
std::vector<Trie*> next;
};
void insert_trie(Trie* root, std::string& word) {
Trie* cur = root;
for (int i = 0; i < word.size(); ++i) {
if (!cur->next[word[i]-'a']) {
cur->next[word[i]-'a'] = new (std::nothrow) Trie;
}
cur = cur->next[word[i]-'a'];
}
cur->end = true;
}
string longestWord(vector<string>& words) {
if (words.size() <= 0) {
return "";
}
Trie* root = new (std::nothrow) Trie;
for (auto& word : words) {
insert_trie(root, word);
}
// 如果长度相等，按照字典序列排序
// 否则按照长度排序
sort(words.begin(), words.end(), [](std::string& w1, std::string& w2) {
if (w1.size() == w2.size()) {
return w1 < w2;
}
return w1.size() > w2.size();
});
for (auto& word : words) {
// false表示排出为自己的字符串
if (can_split(false, word, root)) {
return word;
}
}
return "";
}
private:
bool can_split(bool flag, std::string word, Trie* root) {
Trie* cur = root;
for (int i = 0; i < word.size(); ++i) {
// 如果没有这个字符
if (!cur->next[word[i]-'a']) {
return false;
}
/*if (cur->next[word[i]-'a']->end && i == word.size()-1 && flag) {
return true;
}*/
// 这个字符是结尾，则尝试一下
if (cur->next[word[i]-'a']->end && can_split(true, word.substr(i+1), root)) {
return true;
}
cur = cur->next[word[i]-'a'];
}
// 判断是否已经到了字符串的末尾
return flag && cur->end;
//return false;
}
};