leetcode

0 class Solution {

1 struct Node {

2 Node(){};

3 Node *children[27] = {nullptr};

4 bool &terminate = reinterpret_cast<bool &>(children[0]);

5 };

6

7 public:

8 string replaceWords(const vector<string> &dictionary, const string &sentence) {

9 Node *trie = new Node();

10 for (const string &s : dictionary) {

11 Node *crnt = trie;

12 for (const char c : s) {

13 const int idx = c & 0x1F;

14 if (!crnt->children[idx]) crnt->children[idx] = new Node();

15 crnt = crnt->children[idx];

16 }

17 crnt->terminate = true;

18 }

19

20 string res, word, tmp;

21 stringstream ss(sentence);

22 while (ss >> word) {

23 Node *crnt = trie;

24 for (const char c : word) {

25 const int idx = c & 0x1F;

26 if (!crnt->children[idx] || crnt->terminate) break;

27 crnt = crnt->children[idx];

28 tmp += c;

29 }

30 res += (crnt->terminate ? tmp : word) + ' ';

31 tmp.clear();

32 }

33 res.pop_back();

34 return res;

35 }

36 };