648. 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;
    }
};

• T: $O(D \cdot W + S \cdot W)$
• S: $O(D \cdot W + S \cdot W)$