LeetCode 720. 词典中最长的单词
原题链接
中等
作者:
我是java同学
,
2023-10-15 15:23:52
,
所有人可见
,
阅读 35
class Solution {
public:
struct Node {
bool is_end;
Node* son[26];
Node() {
is_end = false;
for (int i = 0; i < 26; i ++ )
son[i] = NULL;
}
}* root;
void insert(string s, int id) {
auto p = root;
for (auto c: s) {
int u = c - 'a';
if (!p->son[u]) p->son[u] = new Node();
p = p->son[u];
}
p->is_end = true;
}
bool query(string s) {
auto p = root;
for (auto c: s) {
int u = c - 'a';
if (!p->son[u]) return false;
p = p->son[u];
if (!p->is_end) return false;
}
return p->is_end;
}
string longestWord(vector<string>& words) {
root = new Node();
for (int i = 0; i < words.size(); i ++ ) {
insert(words[i], i);
}
string res;
for (auto word: words) {
int n = word.size(), m = res.size();
if (n < m) continue;
if (n == m && word > res) continue;
if (query(word)) res = word;
}
return res;
}
};