LeetCode 648. 单词替换
原题链接
中等
作者:
我是java同学
,
2023-10-15 13:57:42
,
所有人可见
,
阅读 41
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) {
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];
}
return p->is_end;
}
string replaceWords(vector<string>& dictionary, string sentence) {
root = new Node();
for (auto c: dictionary) insert(c);
stringstream ssin(sentence);
string res, word;
while (ssin >> word) {
auto p = root;
string s;
for (auto c: word) {
int u = c - 'a';
s += c;
if (query(s)) break;
}
res += s + ' ';
}
res.pop_back();
return res;
}
};