## 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[26];
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] = 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<string>& dict, string sentence) {
unordered_map<int, unordered_set``````
``` Copy The Code & Input x – + cmd dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery" Output x – + 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) { addWord(word, 0, root); } 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; } addWord(word, idx + 1, root); } } class Node { char c; Map < Character, Node> children; String word; public Node(char c) { this.c = c; children = new HashMap < >(); word = null; } } Copy The Code & Input x – + cmd dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs" Output x – + 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 x – + cmd dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs" Output x – + 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 x – + cmd dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery" Output x – + cmd "the cat was rat by the bat" Advertisements (adsbygoogle = window.adsbygoogle || []).push({}); Demonstration ```
``` #647 Leetcode Palindromic Substrings Solution in C, C++, Java, JavaScript, Python, C# Leetcode #649 Leetcode Dota2 Senate Solution in C, C++, Java, JavaScript, Python, C# Leetcode ```
``` ```