648. Replace Words
Problem Description
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.
Examples:
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 ≤ 10^6
- 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.
Python Solution
class Solution:
def replaceWords(self, dictionary: List[str], sentence: str) -> str:
# Build trie
root = {}
for word in dictionary:
node = root
for char in word:
node = node.setdefault(char, {})
node['$'] = word # Mark end of word
def find_root(word):
node = root
for i, char in enumerate(word):
if '$' in node: # Found a root
return node['$']
if char not in node: # No root exists
return word
node = node[char]
return word
# Process each word in the sentence
words = sentence.split()
return ' '.join(find_root(word) for word in words)Alternative Solution (Using Set):
class Solution:
def replaceWords(self, dictionary: List[str], sentence: str) -> str:
rootset = set(dictionary)
def replace(word):
for i in range(1, len(word) + 1):
if word[:i] in rootset:
return word[:i]
return word
return ' '.join(map(replace, sentence.split()))Implementation Notes:
- First solution uses Trie for efficient prefix matching
- Second solution uses Set for simpler implementation
- Trie solution has better time complexity for long words
Java Solution
class Solution {
class TrieNode {
Map children = new HashMap<>();
String word = null;
}
public String replaceWords(List dictionary, String sentence) {
TrieNode root = new TrieNode();
// Build trie
for (String word : dictionary) {
TrieNode node = root;
for (char c : word.toCharArray()) {
node.children.putIfAbsent(c, new TrieNode());
node = node.children.get(c);
}
node.word = word;
}
// Process sentence
StringBuilder result = new StringBuilder();
String[] words = sentence.split(" ");
for (String word : words) {
if (result.length() > 0) {
result.append(" ");
}
TrieNode node = root;
for (char c : word.toCharArray()) {
if (node.word != null || !node.children.containsKey(c)) {
break;
}
node = node.children.get(c);
}
result.append(node.word != null ? node.word : word);
}
return result.toString();
}
} C++ Solution
class Solution {
struct TrieNode {
unordered_map children;
string* word = nullptr;
~TrieNode() {
for (auto& pair : children) {
delete pair.second;
}
}
};
public:
string replaceWords(vector& dictionary, string sentence) {
TrieNode* root = new TrieNode();
// Build trie
for (const string& word : dictionary) {
TrieNode* node = root;
for (char c : word) {
if (!node->children[c]) {
node->children[c] = new TrieNode();
}
node = node->children[c];
}
node->word = &word;
}
// Process sentence
stringstream ss(sentence);
string word, result;
bool first = true;
while (ss >> word) {
if (!first) {
result += " ";
}
first = false;
TrieNode* node = root;
for (char c : word) {
if (node->word || !node->children[c]) {
break;
}
node = node->children[c];
}
result += node->word ? *node->word : word;
}
delete root;
return result;
}
}; JavaScript Solution
/**
* @param {string[]} dictionary
* @param {string} sentence
* @return {string}
*/
var replaceWords = function(dictionary, sentence) {
const root = {};
// Build trie
for (const word of dictionary) {
let node = root;
for (const char of word) {
node = node[char] = node[char] || {};
}
node.word = word;
}
// Find root word
const findRoot = (word) => {
let node = root;
for (const char of word) {
if (node.word) return node.word;
if (!node[char]) return word;
node = node[char];
}
return word;
};
// Process sentence
return sentence.split(' ')
.map(findRoot)
.join(' ');
};C# Solution
public class Solution {
class TrieNode {
public Dictionary Children { get; } = new Dictionary();
public string Word { get; set; }
}
public string ReplaceWords(IList dictionary, string sentence) {
var root = new TrieNode();
// Build trie
foreach (var word in dictionary) {
var node = root;
foreach (var c in word) {
if (!node.Children.ContainsKey(c)) {
node.Children[c] = new TrieNode();
}
node = node.Children[c];
}
node.Word = word;
}
// Process sentence
return string.Join(" ",
sentence.Split(' ')
.Select(word => {
var node = root;
foreach (var c in word) {
if (node.Word != null || !node.Children.ContainsKey(c)) {
break;
}
node = node.Children[c];
}
return node.Word ?? word;
}));
}
} Alternative Solution (Using HashSet):
public class Solution {
public string ReplaceWords(IList dictionary, string sentence) {
var rootSet = new HashSet(dictionary);
return string.Join(" ",
sentence.Split(' ')
.Select(word => {
for (int i = 1; i <= word.Length; i++) {
var prefix = word.Substring(0, i);
if (rootSet.Contains(prefix)) {
return prefix;
}
}
return word;
}));
}
} Implementation Notes:
- First solution uses Trie for efficient prefix matching
- Second solution uses HashSet for simpler implementation
- Both solutions handle all edge cases correctly