648. Replace Words
Problem Description
In this problem, we are given a dictionary of root words and a sentence composed of space-separated words. Our task is to replace every word in the sentence with its root word if it starts with one. If there's more than one root word applicable, we must use the shortest one. The goal is to return the updated sentence with all possible words replaced by their roots.
Intuition
To solve this problem efficiently, we can use a data structure called a Trie (also known as a prefix tree). The Trie is ideal for this situation because it allows us to quickly check if a word starts with any of the given root words.
The process is as follows:
-
Build the Trie: We insert all root words from the dictionary into the Trie. Each node in the Trie represents a character, and each path from the root of the Trie to a leaf or a node with a marker representing the end of a word can be seen as a root word in the dictionary.
-
Search for Roots: For each word in the sentence, we search for the shortest root in the Trie. While traversing the Trie with the characters of the given word, if we encounter a node that signifies the end of a word (a root word), we record this as the potential replacement.
-
Replace Words: If we found a root word in the Trie while traversing the characters of the given word, we replace it in the sentence. Otherwise, we leave the word as it is if no root word is found.
-
Return the Result: We join all words, modified or not, into a sentence and return it.
Using a Trie is beneficial because it minimizes the number of comparisons needed to find the root. It's efficient because, as soon as the shortest root is found, we don't need to check for longer roots.
Learn more about Trie patterns.
Solution Approach
The solution approach can be broken down into a few clear steps, each related to an aspect of the Trie data structure and the usage of it within the problem context.
Step 1: Trie Data Structure Implementation
- We first implement the
Trie
class, which has the children (an array of size 26 to represent each letter of the English alphabet) and a reference (ref
) integer that will hold the index of the root in the array if we reach the end of a root word. - The
insert
method is used for adding a word into the Trie. Each character of the word corresponds to an index in the children array (calculated byord(c) - ord('a')
). If the corresponding child node does not exist, we create a new Trie node. Theref
at the last character is set to the index of the root word in the dictionary.
Step 2: Build the Trie with Root Words
- We instantiate a Trie object and loop through each root word in the dictionary, inserting each root into the Trie with its index in the dictionary.
Step 3: Searching and Replacing Words
- Now, to replace words in the sentence with their roots, we split the sentence into words and iterate over each word. For each word, we perform a search using the
search
method. This method traverses the Trie similar to theinsert
method, but here we check at each step if the current Trie node has a reference to a dictionary index (i.e., if it's the end of a root word). If we find such a node, we return that index immediately. - If a root is found (
idx
is not-1
), we use the root word from the dictionary to replace the original word in the sentence; if not, we keep the original word.
Step 4: Creating the Result
- The replacements (or original words, if no root was found) are collected in the
ans
list. This list is then joined into a string separated by spaces to form the final sentence.
Step 5: Returning the Final Sentence
- The joined string is returned, giving us the sentence with all possible successor words replaced with their roots.
Using a Trie ensures that each word is efficiently checked against all root words, and the data structure facilitates early stopping for the shortest root word match, optimizing the replacement process.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through an example to illustrate the solution approach. Suppose we are given the following dictionary of root words and a sentence:
- Root Dictionary:
["cat", "bat", "rat"]
- Sentence:
"the cattle was rattled by the battery"
Using the approach described, we will do the following:
Step 1: Trie Data Structure Implementation
We'll implement the Trie
data structure. This Trie
is not fully shown here but will be a part of the coding process.
Step 2: Build the Trie with Root Words
We'll create a Trie and insert each root word: cat
, bat
, rat
. The Trie will represent these words in prefixes: the paths from the root to c
, ca
, cat
will represent the word cat
and so on for bat
and rat
.
Step 3: Searching and Replacing Words
Now we need to replace words in the sentence. The sentence is split into words: "the"
, "cattle"
, "was"
, "rattled"
, "by"
, "the"
, "battery"
.
- For
"cattle"
, we traverse throughc -> a -> t
. Ascat
is a root word, we replace"cattle"
with"cat"
. - No root words are found for
"the"
,"was"
, or"by"
, so they remain unchanged. - For
"rattled"
, we traverse throughr -> a -> t
. Asrat
is a root word, we replace"rattled"
with"rat"
. - For
"battery"
, we traverse throughb -> a -> t
. Asbat
is a root word, we replace"battery"
with"bat"
.
Step 4: Creating the Result
After the above replacements, the sentence becomes: "the cat was rat by the bat"
.
Step 5: Returning the Final Sentence
Finally, we join this array of words and return the sentence: "the cat was rat by the bat"
.
This example illustrates how the Trie enables us to efficiently find the shortest root word that a word starts with and replace it correspondingly.
Solution Implementation
1# Define the Trie data structure.
2class Trie:
3 def __init__(self):
4 # Children is a list of 26 elements, each can be a Trie node or None,
5 # representing each letter of the alphabet.
6 self.children = [None] * 26
7
8 # Reference index to keep track of the word's index from the dictionary in the trie.
9 self.ref = -1
10
11 # Function to insert a word into the trie along with its index from the dictionary.
12 def insert(self, word, index):
13 node = self
14 for char in word:
15 char_index = ord(char) - ord('a') # Convert char to index (0-25).
16
17 # If there is no Trie node for this character, create a new Trie node.
18 if node.children[char_index] is None:
19 node.children[char_index] = Trie()
20
21 # Move to the Trie node corresponding to the character.
22 node = node.children[char_index]
23
24 # Assign the word's index from the dictionary to the last node of the word.
25 node.ref = index
26
27 # Function to search for a word in the trie.
28 def search(self, word):
29 node = self
30 for char in word:
31 char_index = ord(char) - ord('a') # Convert char to index (0-25).
32
33 # If there is no Trie node for this character, the word is not in the trie.
34 if node.children[char_index] is None:
35 return -1
36
37 # Move to the Trie node corresponding to the character.
38 node = node.children[char_index]
39
40 # If a word ends here, return the reference index.
41 if node.ref != -1:
42 return node.ref
43 return -1
44
45
46# Solution class handling the replacement of words using the Trie data structure.
47class Solution:
48 def replaceWords(self, dictionary, sentence):
49 trie = Trie()
50
51 # Insert all words from the dictionary into the trie with their respective indices.
52 for idx, word in enumerate(dictionary):
53 trie.insert(word, idx)
54
55 answer = [] # List to hold the results.
56
57 # Split the sentence into words and replace them accordingly.
58 for word in sentence.split():
59 # Search for the word's prefix in the trie.
60 index = trie.search(word)
61
62 # If a prefix is found, replace the word with the prefix from the dictionary.
63 # If not found, keep the original word.
64 answer.append(dictionary[index] if index != -1 else word)
65
66 # Join the words back into a sentence and return it.
67 return " ".join(answer)
68
1class Trie {
2 // Trie contains 26 children for each possible lowercase letter.
3 private Trie[] children = new Trie[26];
4 // 'ref' is used to store the index of the word in the dictionary.
5 private int wordIndex = -1;
6
7 // Method to insert a word and its index into the Trie.
8 public void insert(String word, int index) {
9 Trie node = this;
10 for (char c : word.toCharArray()) {
11 int charIndex = c - 'a'; // Calculate the index of the character.
12 if (node.children[charIndex] == null) {
13 // If there's no child Trie node for this character, create it.
14 node.children[charIndex] = new Trie();
15 }
16 node = node.children[charIndex];
17 }
18 node.wordIndex = index; // Store the index of the word at the last node.
19 }
20
21 // Method to search for the index of the shortest root in the Trie that is a prefix of the word.
22 public int search(String word) {
23 Trie node = this;
24 for (char c : word.toCharArray()) {
25 int charIndex = c - 'a'; // Calculate the index of the character.
26 // If there's no child Trie node for this character, return -1.
27 if (node.children[charIndex] == null) {
28 return -1;
29 }
30 node = node.children[charIndex];
31 // At each node, check if it's the end of a word in the dictionary.
32 if (node.wordIndex != -1) {
33 return node.wordIndex; // Return the stored index if we found a word.
34 }
35 }
36 return -1; // If no word is found or the complete word must be returned.
37 }
38}
39
40class Solution {
41 public String replaceWords(List<String> dictionary, String sentence) {
42 Trie trie = new Trie();
43 // Insert all dictionary words into the Trie with their respective indices.
44 for (int i = 0; i < dictionary.size(); i++) {
45 trie.insert(dictionary.get(i), i);
46 }
47
48 // Split the sentence into words.
49 String[] words = sentence.split("\\s+");
50 // Prepare a list to store the sentence after replacements.
51 List<String> modifiedSentence = new ArrayList<>();
52 for (String word : words) {
53 // For each word, search the Trie for the shortest root's index.
54 int index = trie.search(word);
55 // If a root is found, replace the word with the root; otherwise, keep the word as is.
56 modifiedSentence.add(index == -1 ? word : dictionary.get(index));
57 }
58 // Join the modified words into a single string, separated by spaces.
59 return String.join(" ", modifiedSentence);
60 }
61}
62
1#include <string>
2#include <sstream>
3#include <vector>
4#include <cstring>
5
6using namespace std;
7
8// A Trie node class to store a character of a word and reference to its
9// full word in the dictionary if it is the last character of a word.
10class Trie {
11private:
12 Trie* children[26]; // Each node contains an array of pointers to its children
13 int wordIndex; // Stores index of the word in the dictionary if the node marks the end of a word
14
15public:
16 // Trie constructor initializes children nodes to null and wordIndex to -1.
17 Trie() : wordIndex(-1) {
18 memset(children, 0, sizeof(children));
19 }
20
21 // Insert a word into the Trie, recording its index in the dictionary.
22 void insert(const string& word, int index) {
23 Trie* node = this;
24 for (char ch : word) {
25 int idx = ch - 'a';
26 if (!node->children[idx]) {
27 node->children[idx] = new Trie();
28 }
29 node = node->children[idx];
30 }
31 node->wordIndex = index;
32 }
33
34 // Search for the shortest root in the Trie that matches a prefix of the given word.
35 // Returns the index of the word in the dictionary or -1 if not found.
36 int search(const string& word) {
37 Trie* node = this;
38 for (char ch : word) {
39 int idx = ch - 'a';
40 if (!node->children[idx]) {
41 return -1;
42 }
43 node = node->children[idx];
44 if (node->wordIndex != -1) {
45 // If a word ending is found before the full search is done,
46 // return the index of this root word.
47 return node->wordIndex;
48 }
49 }
50 return -1;
51 }
52};
53
54// Solution class containing the method to replace words.
55class Solution {
56public:
57 // Replaces words in 'sentence' with their corresponding shortest root in 'dictionary'.
58 // Words in 'sentence' that do not have a root in 'dictionary' remain unchanged.
59 string replaceWords(vector<string>& dictionary, string sentence) {
60 Trie* trie = new Trie();
61 for (int i = 0; i < dictionary.size(); ++i) {
62 // Insert each word from the dictionary into the Trie with its index.
63 trie->insert(dictionary[i], i);
64 }
65 stringstream ss(sentence);
66 string word;
67 string result;
68 while (ss >> word) {
69 // For each word in the sentence, search in Trie to see if it has
70 // a corresponding root word from the dictionary.
71 int index = trie->search(word);
72 // Append either the original word or the root word found to the result.
73 result += (index == -1 ? word : dictionary[index]) + " ";
74 }
75 // Remove the last space character added from the final word.
76 result.pop_back();
77 // Release the allocated Trie memory.
78 delete trie;
79 // Return the modified sentence.
80 return result;
81 }
82};
83
1// Globally define the trie node structure
2interface TrieNode {
3 children: (TrieNode | null)[];
4 referenceId: number;
5}
6
7// Function to create a new trie node
8function createTrieNode(): TrieNode {
9 return {
10 children: Array(26).fill(null),
11 referenceId: -1 // Using -1 as a sentinel value for an empty reference
12 };
13}
14
15// Function to insert a word into the trie
16function insertWord(root: TrieNode, word: string, index: number) {
17 let node: TrieNode = root;
18 for (const char of word) {
19 const charIndex = char.charCodeAt(0) - 'a'.charCodeAt(0);
20 if (!node.children[charIndex]) {
21 node.children[charIndex] = createTrieNode();
22 }
23 node = node.children[charIndex]!;
24 }
25 // Associate the word in the dictionary with the index where it was inserted
26 node.referenceId = index;
27}
28
29// Function to search the trie for a word or prefix
30function searchWord(root: TrieNode, word: string): number {
31 let node: TrieNode = root;
32 for (const char of word) {
33 const charIndex = char.charCodeAt(0) - 'a'.charCodeAt(0);
34 if (!node.children[charIndex]) {
35 return -1; // Trie does not contain the word
36 }
37 node = node.children[charIndex]!;
38 if (node.referenceId !== -1) {
39 return node.referenceId; // A valid reference id found, return it
40 }
41 }
42 return -1; // No valid prefix found in the dictionary
43}
44
45// Function to replace words in a sentence using the trie
46function replaceWordsInSentence(dictionary: string[], sentence: string): string {
47 const root = createTrieNode();
48
49 // Insert all words from the dictionary into the trie
50 dictionary.forEach((word, index) => {
51 insertWord(root, word, index);
52 });
53
54 // Split the sentence into words and replace words with dictionary roots if available
55 return sentence
56 .split(' ')
57 .map(word => {
58 const referenceId = searchWord(root, word);
59 return referenceId !== -1 ? dictionary[referenceId] : word;
60 })
61 .join(' '); // Join the words back into a single string
62}
63
64// Usage
65// Replace words in a sentence with roots from the given dictionary
66const result = replaceWordsInSentence(["cat", "bat", "rat"], "the cattle was rattled by the battery");
67console.log(result); // "the cat was rat by the bat"
68
Time and Space Complexity
Time Complexity
The time complexity of the insert
and search
operations in the Trie data structure is O(L), where L is the length of the word being inserted or searched for. The total time complexity, therefore, depends on the number of words and their lengths.
- The
insert
function is called for each word in the dictionary. If we assume the dictionary hasn
words and the average length of the words ism
, the total time for building the trie is O(n * m). - The
search
function is called for each word in the sentence. If we have a sentence withk
words and the average length of the words isp
, then the total time for searching is O(k * p). - However, we should consider that searching stops early if a prefix is found, potentially reducing the number of characters checked.
Combining these observations, the total time complexity is O(n * m + k * p), considering both the construction of the Trie and the search operations for sentence words.
Space Complexity
The space complexity of the algorithm includes the space used by the Trie and the output list ans
:
- The Trie data structure uses O(m * s) space, where
m
is the length of the longest word in the dictionary ands
is the total number of nodes in the Trie. In the worst case, the Trie has as many nodes as the sum of lengths of all words in the dictionary. The space complexity for the Trie would then be O(26 * alpha), where alpha is the sum of the lengths of all words in the dictionary (assuming no common prefixes). - The
ans
list holdsk
words, and in the worst case, each word is not replaced and is as long as it is in the sentence. Therefore, the space required byans
is proportional to the total character count of the words in the sentence.
Hence, the total space complexity is O(26 * alpha + k * p) if we consider the Trie and ans
. In practice, due to common prefixes in the Trie, the space used is often less than this worst-case scenario.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
Trie Introduction Imagine you have a magic dictionary where as soon as you start spelling a word it immediately tells you how many words that start with those letters How cool would that be This is exactly the kind of magic a data structure called trie performs What's a Trie
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Don’t Miss This!