1
class Solution {
2
 public:
3
  class trii {
4
   public:
5
    char data;
6
    trii *dict[26];
7
    bool isTerminal;
8

9
    trii() {}
10

11
    trii(char d) {
12
      data = d;
13
      for (int i = 0; i < 26; i++) {
14
        dict[i] = NULL;
15
      }
16
      isTerminal = false;
17
    }
18
  };
19

20
  class tree {
21
   public:
22
    trii *root;
23
    tree() {
24
      root = new trii('\0');
25
    }
26

27
    void insert(string str, trii *node) {
28
      if (str.size() == 0) {
29
        node->isTerminal = true;
30
        return;
31
      }
32
      int index = str[0] - 'a';
33
      if (node->dict[index] == NULL) {
34
        node->dict[index] = new trii(str[0]);
35
      }
36
      insert(str.substr(1), node->dict[index]);
37
    }
38

39
    string find(string str, trii *node, string pre) {
40
      if (node->isTerminal == true) {
41
        return pre;
42
      }
43
      int index = str[0] - 'a';
44
      if (str.size() == 0 || node->dict[index] == NULL) {
45
        return "\0";
46
      }
47
      return find(str.substr(1), node->dict[index], pre + str[0]);
48
    }
49

50
    string replaceWith(string word, trii *node) {
51
      string temp = find(word, node, "");
52
      if (temp != "\0") {
53
        word = temp;
54
      }
55
      return word;
56
    }
57
  };
58

59
  string replaceWords(vector<string> &dictionary, string sentence) {
60
    tree *t = new tree();
61
    for (int i = 0; i < dictionary.size(); i++) {
62
      t->insert(dictionary[i], t->root);
63
    }
64
    string ans = sentence;
65
    sentence = "";
66
    for (int i = 0; i < ans.size(); i++) {
67
      string word = "";
68
      while (i < ans.size() && ans[i] != ' ') {
69
        word += ans[i];
70
        i++;
71
      }
72

73
      sentence += t->replaceWith(word, t->root) + " ";
74
    }
75
    sentence.pop_back();
76
    return sentence;
77
  }
78
};