## [648\. Replace Words](https://leetcode.com/problems/replace-words/)

In English, we have a concept called **root**, which can be followed by some other word to form another longer word - let's call this word **derivative**. For example, when the **root** `"help"` is followed by the word `"ful"`, we can form a derivative `"helpful"`.

Given a `dictionary` consisting of many **roots** and a `sentence` consisting of words separated by spaces, replace all the derivatives in the sentence with the **root** forming it. If a derivative can be replaced by more than one **root**, replace it with the **root** that has **the shortest length**.

Return _the `sentence`_ after the replacement.

**Example 1:**

**Input:** dictionary = \["cat","bat","rat"\], sentence = "the cattle was rattled by the battery"
**Output:** "the cat was rat by the bat"

**Example 2:**

**Input:** dictionary = \["a","b","c"\], sentence = "aadsfasf absbs bbab cadsfafs"
**Output:** "a a b c"

**Constraints:**

- `1 <= dictionary.length <= 1000`
- `1 <= dictionary[i].length <= 100`
- `dictionary[i]` consists of only lower-case letters.
- `1 <= sentence.length <= 106`
- `sentence` consists of only lower-case letters and spaces.
- The number of words in `sentence` is in the range `[1, 1000]`
- The length of each word in `sentence` is in the range `[1, 1000]`
- Every two consecutive words in `sentence` will be separated by exactly one space.
- `sentence` does not have leading or trailing spaces.

class TrieNode {
public:
    TrieNode* child[26];
    bool isWord = false;
    TrieNode() {
        for(int i = 0; i < 26; i++) {
            child[i] = nullptr;
        }
    }
};

class Trie {
private:
    TrieNode* root;

public:
    Trie() {
        root = new TrieNode();
    }

    void insert(string word) {
        TrieNode* node = root;
        for(auto c : word) {
            if(!node->child[c - 'a']) {
                node->child[c - 'a'] = new TrieNode();
            }
            node = node->child[c - 'a'];
        }
        node->isWord = true;
    }

    string searchShortestRoot(string word) {
        TrieNode* node = root;
        // 用一個 prefix 字串儲存最短 root
        string prefix = "";
        for (char c : word) {
            // 當發現沒有在字典樹內的時候，break，並且返回 word
            if (!node->child[c - 'a']) break;
            prefix.push_back(c);
            node = node->child[c - 'a'];
            // 輸入的 word 已經是最短 root 的狀況
            if (node->isWord) return prefix;
        }
        return word;
    }
};

class Solution {
public:
    string replaceWords(vector<string>& dictionary, string sentence) {
        stringstream ss(sentence);
        Trie t;
        // 將 root push 到 trie
        for(auto word : dictionary) {
            t.insert(word);
        }
        string token;
        string res;
        // 用 string stream 的方式尋找 word
        // 如果找到的話，replace word with root
        while (getline(ss, token, ' ')) {
            res += t.searchShortestRoot(token) + " ";
        }
        res.pop_back();
        return res;
    }
};

:::success
- 時間複雜度：$O(d \cdot w + s \cdot w)$
- 空間複雜度：$O(d \cdot w + s \cdot w)$
:::