## Algorithm

Problem Name: 648. Replace Words

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

Given a `dictionary` consisting of many roots and a `sentence` consisting of words separated by spaces, replace all the successors in the sentence with the root forming it. If a successor can be replaced by more than one root, replace it with the root that has the shortest length.

Return the `sentence` after the replacement.

Example 1:

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

Example 2:

```Input: dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
Output: "a a b c"
```

Constraints:

• `1 <= dictionary.length <= 1000`
• `1 <= dictionary[i].length <= 100`
• `dictionary[i]` consists of only lower-case letters.
• `1 <= sentence.length <= 106`
• `sentence` consists of only lower-case letters and spaces.
• The number of words in `sentence` is in the range `[1, 1000]`
• The length of each word in `sentence` is in the range `[1, 1000]`
• Every two consecutive words in `sentence` will be separated by exactly one space.
• `sentence` does not have leading or trailing spaces.

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
typedef struct trie_s {
struct trie_s *prev;
struct trie_s *child;
char *s;
} trie_t;
char c, *str = s;
trie_t *child;
while (c = *(s ++)) {
child = node->child[c - 'a'];
if (!child) {
child = calloc(1, sizeof(trie_t));
//assert(child);
node->child[c - 'a'] = child;
} else if (child->s) {
return;
}
node = child;
}
node->s = str;
}
trie_t *prev;
}
}
trie_t *trie_search(trie_t *node, char *str) {
char c;
while (c = *(str ++)) {
node = node->child[c - 'a'];
if (!node || node->s) return node;
}
return NULL;
}
char* replaceWords(char** dict, int dictSize, char* sentence) {
trie_t root = { 0 }, *node, *link = NULL;
char *p, *substr;

// build a trie
while (dictSize) {
}

p = malloc((strlen(sentence) + 1) * sizeof(char));
//assert(p);
p = 0;

// search each word in the trie
while (*sentence) {
substr = sentence;       // start of a word
while (*sentence && *sentence != ' ') {
sentence ++;
}
if (*sentence == ' ') {
*sentence = 0;
sentence ++;
}
// skip blank spaces
while (*sentence == ' ') sentence ++;

// search
node = trie_search(&root, substr);
if (!node) {
strcat(p, substr);
} else {
strcat(p, node->s);
}
strcat(p, " ");
}
p[strlen(p) - 1] = 0;

return p;
}
``````
Copy The Code &

Input

cmd
dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"

Output

cmd
"the cat was rat by the bat"

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
string replaceWords(vector& dict, string sentence) {
unordered_map>m;
for(string& s: dict) m[s.size()].insert(s);
string res = "";
for(int i = 0, j = 0; i < sentence.size(); i = j + 1, j = i){
string word = "";
for(; j < sentence.size() && sentence[j] != ' '; j++){
string prefix = sentence.substr(i, j - i + 1);
if(m[prefix.size()].count(prefix) && word.empty()) word = prefix;
}
if(word.empty() && j != i) word = sentence.substr(i, j - i);
res += word + " ";
}
res.pop_back();
return res;
}
};
``````
Copy The Code &

Input

cmd
dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"

Output

cmd
"the cat was rat by the bat"

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public String replaceWords(List dict, String sentence) {
Node root = new Node('-');
for (String word : dict) {
}
String[] words = sentence.split("\\s+");
for (int i = 0; i < words.length; i++) {
String prefix = getPrefix(words[i], root);
if (prefix != null) {
words[i] = prefix;
}
}
return String.join(" ", words);
}

private String getPrefix(String word, Node root) {
for (int i = 0; i < word.length(); i++) {
if (!root.children.containsKey(word.charAt(i))) {
return null;
}
root = root.children.get(word.charAt(i));
if (root.word != null) {
return root.word;
}
}
return null;
}

private void addWord(String word, int idx, Node root) {
if (idx == word.length()) {
return;
}
if (!root.children.containsKey(word.charAt(idx))) {
root.children.put(word.charAt(idx), new Node(word.charAt(idx)));
}
root = root.children.get(word.charAt(idx));
if (idx == word.length() - 1) {
root.word = word;
}
}
}

class Node {
char c;
Map children;
String word;

public Node(char c) {
this.c = c;
children = new HashMap<>();
word = null;
}
}
``````
Copy The Code &

Input

cmd

Output

cmd
"a a b c"

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const replaceWords = function(dict, sentence) {
dict.sort();
const unsortedParts = sentence.split(" ");
const parts = unsortedParts.slice();
parts.sort();

let i = (j = 0);
const rootMap = {};
while (i < dict.length && j < parts.length) {
let part = parts[j];
let root = dict[i];
// dict is ahead, increase part
if (root > part) {
j++;
} else {
if (part.startsWith(root)) {
rootMap[part] = root;
j++;
} else {
i++;
}
}
}
for (i = 0; i < unsortedParts.length; i++) {
if (rootMap[unsortedParts[i]]) {
unsortedParts[i] = rootMap[unsortedParts[i]];
}
}
return unsortedParts.join(" ");
};

console.log(
replaceWords(["cat", "bat", "rat"], "the cattle was rattled by the battery")
);
``````
Copy The Code &

Input

cmd

Output

cmd
"a a b c"

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def replaceWords(self, dict, sentence):
"""
:type dict: List[str]
:type sentence: str
:rtype: str
"""
s = set(dict)
sentence = sentence.split()
for j, w in enumerate(sentence):
for i in range(1, len(w)):
if w[:i] in s:
sentence[j] = w[:i]
break
return " ".join(sentence)
``````
Copy The Code &

Input

cmd
dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"

Output

cmd
"the cat was rat by the bat"