Algorithm
Problem Name: 648. Replace Words
Problem Link: https://leetcode.com/problems/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 <= 10001 <= dictionary[i].length <= 100dictionary[i]consists of only lower-case letters.1 <= sentence.length <= 106sentenceconsists of only lower-case letters and spaces.- The number of words in
sentenceis in the range[1, 1000] - The length of each word in
sentenceis in the range[1, 1000] - Every two consecutive words in
sentencewill be separated by exactly one space. sentencedoes 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;
void add2trie(trie_t *node, char *s, trie_t **link_p) {
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);
child->prev = *link_p;
*link_p = child;
node->child[c - 'a'] = child;
} else if (child->s) {
return;
}
node = child;
}
node->s = str;
}
void trie_free(trie_t *link) {
trie_t *prev;
while (link) {
prev = link->prev;
free(link); // oj fails here!!!
link = 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) {
add2trie(&root, dict[-- dictSize], &link);
}
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;
trie_free(link);
return p;
}
Input
dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
Output
"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_setInput
dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
Output
"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;
}
}
Input
dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
Output
"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")
);
Input
dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
Output
"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)
Input
dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
Output
"the cat was rat by the bat"