648. Replace Words

In English, we have a concept called root, which can be followed by some other words to form another longer word - let's call this word successor. For example, the root an, followed by other, which can form another word another.

Now, given a dictionary consisting of many roots and a sentence. You need to replace all the successor in the sentence with the root forming it. If a successor has many roots can form it, replace it with the root with the shortest length.

You need to output the sentence after the replacement.

Example 1:

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

Note:

1. The input will only have lower-case letters.

2. 1 <= dict words number <= 1000

3. 1 <= sentence words number <= 1000

4. 1 <= root length <= 100

5. 1 <= sentence words length <= 1000

class TrieNode {
public:
    TrieNode() : next(vector<TrieNode*>(26, nullptr)), isWord(false) {}
    vector<TrieNode*> next;
    bool isWord;
};
void buildTrie(TrieNode* root, const string& word) {
    TrieNode* cur = root;
    for (const char& ch : word) {
        int idx = ch - 'a';
        if (!cur->next[idx]) cur->next[idx] = new TrieNode();
        cur = cur->next[idx];
    }
    cur->isWord = true;
}
string findPrefix(TrieNode* node, const string& word) {
    string res;
    for (const char& ch : word) {
        int idx = ch - 'a';
        if (!node->next[idx]) break;
        res += ch;
        node = node->next[idx];
        if (node->isWord) return res;
    }
    return word;
}
string replaceWords(vector<string>& dict, string sentence) {
    string res, tmp;
    istringstream iss(sentence);
    TrieNode* root = new TrieNode();
    for (const string& word : dict) {
        buildTrie(root, word);
    }
    while (iss >> tmp) {
        if (!res.empty()) res += " ";
        res += findPrefix(root, tmp);
    }
    delete root;
    return res;
}