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:

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 = {};
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;
}
}