648. Replace Words

MediumTrieArrayHash TableString
Leetcode Link

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:

  1. 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.

  2. 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.

  3. 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.

  4. 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Which of these pictures shows the visit order of a depth-first search?

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 by ord(c) - ord('a')). If the corresponding child node does not exist, we create a new Trie node. The ref 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 the insert 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of these properties could exist for a graph but not a tree?

Example 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 through c -> a -> t. As cat 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 through r -> a -> t. As rat is a root word, we replace "rattled" with "rat".
  • For "battery", we traverse through b -> a -> t. As bat 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.

Not Sure What to Study? Take the 2-min Quiz:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Python Solution

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

Java Solution

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

C++ Solution

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

Typescript Solution

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
Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

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 has n words and the average length of the words is m, 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 with k words and the average length of the words is p, 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 and s 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 holds k 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 by ans 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.


Recommended Readings