648. Replace Words

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