Formatted question description: https://leetcode.ca/all/648.html

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/

// 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;
    }
};

Java

class Solution {
    TrieNode root = new TrieNode();

    public String replaceWords(List<String> dict, String sentence) {
        createTrie(dict);
        String[] array = sentence.split(" ");
        int length = array.length;
        for (int i = 0; i < length; i++) {
            int prefixLength = searchPrefix(array[i]);
            if (prefixLength > 0)
                array[i] = array[i].substring(0, prefixLength);
        }
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < length; i++)
            sb.append(array[i] + " ");
        sb.deleteCharAt(sb.length() - 1);
        return sb.toString();
    }

    public void createTrie(List<String> dict) {
        for (String prefix : dict) {
            TrieNode node = root;
            int length = prefix.length();
            for (int i = 0; i < length; i++) {
                char letter = prefix.charAt(i);
                int index = letter - 'a';
                if (node.next[index] == null)
                    node.next[index] = new TrieNode();
                node = node.next[index];
            }
            node.isEnd = true;
        }
    }

    public int searchPrefix(String word) {
        TrieNode node = root;
        int length = word.length();
        for (int i = 0; i < length; i++) {
            char letter = word.charAt(i);
            int index = letter - 'a';
            if (node.isEnd)
                return i;
            else if (node.next[index] == null)
                return 0;
            else
                node = node.next[index];
        }
        return node.isEnd ? length : 0;
    }
}

class TrieNode {
    boolean isEnd;
    TrieNode[] next;

    public TrieNode() {
        isEnd = false;
        next = new TrieNode[26];
    }
}

All Problems

All Solutions