Leetcode 648. Replace Words

Problem Explanation:

In this problem, we are given a list of roots, and a sentence. We are required to replace all successors in the sentence with the root if the root forms it. A successor is a longer word formed by a root being followed by some other words. If a successor has many roots that can form it, replace it with the one with the shortest length. After replacing the successors, we then return the new modified sentence. A root and the sentence only consist of lower-case letters.

Let's take an example:

For instance, given dictionary = ["cat", "bat", "rat"] and a sentence = "the cattle was rattled by the battery" We can form "cattle" with root "cat", "rattled" with root "rat" and "battery" with root "bat". So, we replace these three words with the roots they have been formed from. The result will be : "the cat was rat by the bat"

Solution Approach:

This problem can be solved using Trie data structure. We start by creating a Trie and inserting all the roots from the given dictionary into the Trie. After that, we split the sentence into words and search each word in the Trie. If a word exists in the Trie, we replace that word with the root from the Trie, otherwise, we keep the word as it is.

Detailed Steps:

1. First, we build the Trie with all the words from the dictionary.
2. Then, we start reading the sentence word by word.
3. For each word, we search it in the Trie. We stop at the node where the root ends or the word ends, whichever comes first.
4. If the node we stopped has a root ending, we replace the word with the root, else, we keep the word as it is.
5. We repeat the steps 3 and 4 for all words in the sentence.

Let's take an example to illustrate the steps:

Example: dict = ["cat", "bat", "rat"] sentence = "the cattle was rattled by the battery"

After inserting all the words from dict into Trie, it would be something like this: 'c' -> 'a' -> 't' 'b' -> 'a' -> 't' 'r' -> 'a' -> 't'

Now, we start reading the sentence word by word. For example, we read the first word "the". We start searching for this word in Trie and it doesn't exist. So we keep "the" as it is. Next we read "cattle". It exists in Trie, where 'c' -> 'a' -> 't' and then the word ends in Trie after 't'. So, we replace "cattle" with "cat". We do the same for every word in the sentence. The output will be "the cat was rat by the bat".Python Solution

Our Python solution involves creating a Trie data structure along with TrieNode class which will store each character of the root words. In the Trie, we'll have an insert method to add the roots into the Trie and a replace method to replace successors in the sentence with the roots.

1
2Python
3class TrieNode:
4    def __init__(self):
5        self.children = collections.defaultdict(TrieNode)
6        self.end = False
7
8class Trie:
9    def __init__(self):
10        self.root = TrieNode()
11
12    def insert(self, word):
13        node = self.root
14        for char in word:
15            node = node.children[char]
16        node.end = word
17
18    def replace(self, word):
19        node = self.root
20        for i, char in enumerate(word):
21            if char not in node.children:
22                break
23            node = node.children[char]
24            if node.end:
25                return node.end
26        return word
27
28class Solution:
29    def replaceWords(self, roots, sentence):
30        trie = Trie()
31        for root in roots:
32            trie.insert(root)
33        sentence = sentence.split()
34        for i, word in enumerate(sentence):
35            sentence[i] = trie.replace(word)
36        return ' '.join(sentence)
37
38roots = ["cat", "bat", "rat"]
39sentence = "the cattle was rattled by the battery"
40print(Solution().replaceWords(roots, sentence))  # Output: "the cat was rat by the bat"

Java Solution

Similar to Python, we'll define a Trie and TrieNode class in Java for handling our operations.

1
2Java
3public class TrieNode {
4    TrieNode[] children;
5    String word;
6    
7    public TrieNode() {
8        children = new TrieNode[26];
9    }
10}
11
12public class Solution {
13    public String replaceWords(List<String> roots, String sentence) {
14        TrieNode trie = new TrieNode();
15        for(String root: roots){
16            TrieNode node = trie;
17            for(char letter: root.toCharArray()){
18                if(node.children[letter-'a'] == null){
19                    node.children[letter-'a'] = new TrieNode();
20                }
21                node = node.children[letter-'a'];
22            }
23            node.word = root;
24        }
25
26        StringBuilder result = new StringBuilder();
27        for(String word: sentence.split("\\s+")){
28            TrieNode node = trie;
29            for(char letter: word.toCharArray()){
30                if(node.children[letter-'a'] == null || node.word != null){
31                    break;
32                }
33                node = node.children[letter-'a'];
34            }
35            result.append(" ");
36            result.append(node.word != null ? node.word : word);
37        }
38
39        return result.deleteCharAt(0).toString();
40    }
41}

In the Java solution, you can call replaceWords() with the list of roots and the sentence to return the modified sentence.

Javascript Solution In Javascript, the approach is the same. We create Trie and TrieNode classes and include methods to insert words into the trie and replace words in the sentences.

1
2Javascript
3class TrieNode {
4  constructor() {
5    this.children = {};
6    this.end = false;
7  }
8}
9
10class Trie {
11  constructor() {
12    this.root = new TrieNode();
13  }
14
15  insert(word) {
16    let node = this.root;
17    for (let char of word) {
18      if (!node.children[char]) {
19        node.children[char] = new TrieNode();
20      }
21      node = node.children[char];
22    }
23    node.end = word;
24  }
25
26  replace(word) {
27    let node = this.root;
28    for (let char of word) {
29      if (!node.children[char] || node.end) {
30        break;
31      }
32      node = node.children[char];
33    }
34    return node.end || word;
35  }
36}
37
38function replaceWords(roots, sentence) {
39  const trie = new Trie();
40  for (let root of roots) {
41    trie.insert(root);
42  }
43  return sentence
44    .split(" ")
45    .map((word) => trie.replace(word))
46    .join(" ");
47}
48
49console.log(replaceWords(["cat", "bat", "rat"], "the cattle was rattled by the battery")); // Output: "the cat was rat by the bat"

All of these solutions have a time complexity of O(n) where n is the length of the sentence.