In this guide, you will get 648. Replace Words LeetCode Solution with the best time and space complexity. The solution to Replace Words problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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 derivative. For example, when the root “help” is followed by the word “ful”, we can form a derivative “helpful”.
Given a dictionary consisting of many roots and a sentence consisting of words separated by spaces, replace all the derivatives in the sentence with the root forming it. If a derivative 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.
struct TrieNode {
vector<shared_ptr<TrieNode>> children;
const string* word = nullptr;
TrieNode() : children(26) {}
};
class Solution {
public:
string replaceWords(vector<string>& dictionary, string sentence) {
for (const string& word : dictionary)
insert(word);
string ans;
istringstream iss(sentence);
for (string s; iss >> s;)
ans += search(s) + ' ';
ans.pop_back();
return ans;
}
private:
shared_ptr<TrieNode> root = make_shared<TrieNode>();
void insert(const string& word) {
shared_ptr<TrieNode> node = root;
for (const char c : word) {
const int i = c - 'a';
if (node->children[i] == nullptr)
node->children[i] = make_shared<TrieNode>();
node = node->children[i];
}
node->word = &word;
}
string search(const string& word) {
shared_ptr<TrieNode> node = root;
for (const char c : word) {
if (node->word)
return *node->word;
const int i = c - 'a';
if (node->children[i] == nullptr)
return word;
node = node->children[i];
}
return word;
}
}; /* code provided by PROGIEZ */
648. Replace Words LeetCode Solution in Java
class TrieNode {
private TrieNode[] children = new TrieNode[26];
private String word;
}
class Solution {
public String replaceWords(List<String> dictionary, String sentence) {
StringBuilder sb = new StringBuilder();
for (final String word : dictionary)
insert(word);
final String[] words = sentence.split(" ");
for (final String word : words)
sb.append(' ').append(search(word));
return sb.substring(1).toString();
}
private TrieNode root = new TrieNode();
private void insert(final String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
final int i = c - 'a';
if (node.children[i] == null)
node.children[i] = new TrieNode();
node = node.children[i];
}
node.word = word;
}
private String search(final String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
if (node.word != null)
return node.word;
final int i = c - 'a';
if (node.children[i] == null)
return word;
node = node.children[i];
}
return word;
}
} // code provided by PROGIEZ
648. Replace Words LeetCode Solution in Python
class Solution:
def __init__(self):
self.root = {}
def insert(self, word: str) -> None:
node = self.root
for c in word:
if c not in node:
node[c] = {}
node = node[c]
node['word'] = word
def search(self, word: str) -> str:
node = self.root
for c in word:
if 'word' in node:
return node['word']
if c not in node:
return word
node = node[c]
return word
def replaceWords(self, dictionary: list[str], sentence: str) -> str:
for word in dictionary:
self.insert(word)
words = sentence.split(' ')
return ' '.join([self.search(word) for word in words]) # code by PROGIEZ
