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"

Solution: Trie

We can use trie to store prefix. We store all words from dictionary to trie. We use istringstream to extract word from sentence.

The key part is to return the shortest prefix. When searching for prefix, we keep adding current node's val to the string, return once we found a prefix

Optimization: To return the shortest prefix of each word, we don't need to insert the whole word. The insertion function will stop once a word has been found.

class Solution {
public:
    class TrieNode {
    public:
        TrieNode(): isWord(false) {};
        unordered_map<char, TrieNode*> child;
        bool isWord;
    };

    void insert(TrieNode* root, string word) {
        TrieNode *cur = root;
        for (char ch : word) {
            if (cur->isWord) return;
            if (!cur->child[ch]) {
                cur->child[ch] = new TrieNode();
            }
            cur = cur->child[ch];
        }
        cur->isWord = true;
    }

    string findPrefix(TrieNode* node, string word) {
        string cur = "";
        for (char c : word) {
            if (!node->child[c]) break;
            cur.push_back(c);
            node = node->child[c];
            if (node->isWord) return cur;
        }
        return word;
    }

    string replaceWords(vector<string>& dict, string sentence) {
        string res = "", t = "";
        istringstream is(sentence);
        TrieNode *root = new TrieNode();
        for (string word : dict) {
            insert(root, word);
        }

        while (is >> t) {
            if (!res.empty()) res += " ";
            res += findPrefix(root, t);
        }
        return res;
    }
};