648. Replace Words

648. Replace Words (Medium)

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

 

Companies:
Uber, Adobe

Related Topics:
Hash Table, Trie

Solution 1. Trie

// OJ: https://leetcode.com/problems/replace-words/
// Author: github.com/lzl124631x
// Time: O(D + S) where D is size of all contents in dictionary, S is size of all contents in sentence
// Space: O(D)
class TrieNode {
public:
    TrieNode *next[26] = {};
    bool isWord = false;
};
class Trie {
private:
    TrieNode root;
public:
    void insert(string &s) {
        auto node = &root;
        for (char c : s) {
            if (!node->next[c - 'a']) node->next[c - 'a'] = new TrieNode();
            node = node->next[c - 'a'];
        }
        node->isWord = true;
    }
    string getWord(string &s) {
        auto node = &root;
        for (int i = 0; i < s.size(); ++i) {
            if (!node->next[s[i] - 'a']) return s;
            node = node->next[s[i] - 'a'];
            if (node->isWord) return s.substr(0, i + 1);
        }
        return s;
    }
};
class Solution {
public:
    string replaceWords(vector<string>& dict, string sentence) {
        istringstream ss(sentence);
        string word, ans;
        Trie trie;
        for (auto s : dict) trie.insert(s);
        while (ss >> word) ans += trie.getWord(word)+ " ";
        ans.pop_back();
        return ans;
    }
};