Vultr DocsLatest Content

Replace Words

Updated on 23 June, 2025
Replace Words header image

Problem Statement

In the English language, a root word can be expanded into a longer word, known as a derivative, by adding more letters to it. This task involves identifying such derivatives in a given sentence and replacing them with their corresponding root word. The source of root words is provided as a dictionary. When replacing a derivative with roots, if multiple roots can form the derivative, the shortest root is chosen for replacement to keep the modified sentence concise. The problem requires processing each word in the sentence and transforming it as necessary according to the rules defined by the dictionary before outputting the full amended sentence.

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 <= 106
  • 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.

Approach and Intuition

  1. Understanding the Problem:

    • The objective is to replace longer words in the sentence with the shortest possible root word from the dictionary that matches the prefix of these words.

  2. Breaking Down the Steps:

    • Read the Input: Start by extracting the roots from the dictionary and the words from the sentence.
    • Check Each Word: For each word in the sentence, determine if it begins with any of the root words in the dictionary.
    • Select the Appropriate Root: If a word starts with multiple roots, select the shortest root. If no roots are applicable, the word remains unchanged.
    • Construct the New Sentence: As each word is processed, construct the new sentence from these words to form the final output.

  3. Important Considerations from Constraints:

    • The approach must efficiently handle cases where the sentence is long (up to 1,000,000 characters) and the dictionary has up to 1,000 roots, ensuring that the replacement process is not overly time-consuming.
    • It’s critical to ensure that the matching process for roots to words is optimal, possibly suggesting the use of a prefix tree or similar data structure for quick lookup.
    • Given the consistency in word and sentence construction, special cases like punctuation do not need to be considered.

By following the above steps systematically, every derivative in the sentence can be replaced with the shortest matching root from the dictionary, ensuring that the end result is as concise and accurate as possible.

Solutions

  • C++
  • Java
  • Python
cpp 
class PrefixTreeNode {
public:
    bool endOfWord;
    vector<PrefixTreeNode*> childNodes;

    PrefixTreeNode() : childNodes(26, nullptr) { endOfWord = false; }
};

class PrefixTree {
private:
    PrefixTreeNode* rootNode;

public:
    PrefixTree() { rootNode = new PrefixTreeNode(); }

    void append(string element) {
        PrefixTreeNode* node = rootNode;
        for (char ch : element) {
            if (node->childNodes[ch - 'a'] == nullptr) {
                node->childNodes[ch - 'a'] = new PrefixTreeNode();
            }
            node = node->childNodes[ch - 'a'];
        }
        node->endOfWord = true;
    }

    string findPrefix(string element) {
        PrefixTreeNode* node = rootNode;
        for (int idx = 0; idx < element.length(); ++idx) {
            char ch = element[idx];
            if (node->childNodes[ch - 'a'] == nullptr) {
                return element;
            }
            node = node->childNodes[ch - 'a'];
            if (node->endOfWord) {
                return element.substr(0, idx + 1);
            }
        }
        return element;
    }
};

class Solution {
public:
    string replaceWords(vector<string>& roots, string statement) {
        istringstream sStream(statement);

        PrefixTree prefixTree;
        for (string root : roots) {
            prefixTree.append(root);
        }

        string segment;
        string result;
        while (getline(sStream, segment, ' ')) {
            result += prefixTree.findPrefix(segment) + " ";
        }

        result.pop_back();  // Remove the last extra space
        return result;
    }
};

In the provided code, the goal is to replace words in a given sentence with the shortest possible roots from a list of root words using a trie (prefix tree) for efficient search. The code is implemented in C++ and can be broken down into several components:

  • PrefixTreeNode: This class represents each node in the trie. Each node has a flag to indicate if it is the end of a word and an array of pointers for its children.

  • PrefixTree: This class handles operations on the trie. It includes:

    • A method to add words to the trie (append), which iterates character by character through each word and adds it to the trie.
    • A method to find the shortest root in the trie that is a prefix of a given word (findPrefix).

  • Solution:

    • The replaceWords function utilizes the PrefixTree to replace each word in the input sentence with the shortest root from the list if one exists.
    • The function reads the sentence word by word and replaces each word with the result from PrefixTree.findPrefix.

Step-by-step process for word replacement:

  1. Initialize a PrefixTree.
  2. Add all the root words to the trie using the append function.
  3. For each word in the input sentence, use the findPrefix function to check if a root word is a prefix of the current word.
  4. Construct the final output by concatenating the replaced words, ensuring that trivial white spaces are handled effectively.

The final result is a modified sentence where each word is replaced by the shortest corresponding root word from the given list of roots if such a prefix match exists. The use of a trie data structure ensures that this lookup is efficient, especially beneficial when there are numerous root words and a long sentence.

java 
class PrefixTreeNode {

    boolean isTerminal;
    PrefixTreeNode[] offspring;

    PrefixTreeNode() {
        isTerminal = false;
        offspring = new PrefixTreeNode[26];
    }
}

class PrefixTree {

    private PrefixTreeNode rootNode;

    public PrefixTree() {
        rootNode = new PrefixTreeNode();
    }

    public void add(String term) {
        PrefixTreeNode traverse = rootNode;
        for (char letter : term.toCharArray()) {
            if (traverse.offspring[letter - 'a'] == null) {
                traverse.offspring[letter - 'a'] = new PrefixTreeNode();
            }
            traverse = traverse.offspring[letter - 'a'];
        }
        traverse.isTerminal = true;
    }

    public String findShortestPrefix(String term) {
        PrefixTreeNode traverse = rootNode;
        for (int index = 0; index < term.length(); index++) {
            char letter = term.charAt(index);
            if (traverse.offspring[letter - 'a'] == null) {
                return term;
            }
            traverse = traverse.offspring[letter - 'a'];
            if (traverse.isTerminal) {
                return term.substring(0, index + 1);
            }
        }
        return term;
    }
}

class Solution {

    public String replaceWords(List<String> roots, String sentence) {
        String words[] = sentence.split(" ");

        PrefixTree rootTree = new PrefixTree();
        for (String root : roots) {
            rootTree.add(root);
        }

        for (int i = 0; i < words.length; i++) {
            words[i] = rootTree.findShortestPrefix(words[i]);
        }

        return String.join(" ", words);
    }
}

The provided solution implements a method to replace words in a sentence with their corresponding shortest prefixes using a custom prefix tree (trie) structure in Java. Here's how it works:

  • Define PrefixTreeNode: This is a basic unit for the Trie, which includes an array to hold children nodes and a boolean to mark the end of a word.

  • Define PrefixTree: This class encapsulates the root node and provides methods to add words to the Trie and to find the shortest prefix of a given word.

    1. Adding Words: Iterate through each character of the word, navigating and creating nodes as necessary.
    2. Finding Shortest Prefix: Traverse the Trie based on each character of the word. If a terminal node is reached (a complete word is formed), return the substring up to that point.

  • In the Solution class:

    1. Split the sentence into words.
    2. Initialize and populate the PrefixTree with a list of root words.
    3. Replace each word in the original sentence with the shortest prefix found in the Trie.
    4. Reconstruct the sentence using the modified words.

This approach provides an efficient way of handling word replacements using Trie data structure, especially useful when there is a frequent need to find or replace prefixes in strings.

python 
class PrefixNode:
    def __init__(self):
        self.complete_word = False
        self.child_nodes = [None] * 26

class PrefixTree:
    def __init__(self):
        self.base = PrefixNode()

    def add_word(self, term):
        node = self.base
        for char in term:
            idx = ord(char) - ord('a')
            if node.child_nodes[idx] is None:
                node.child_nodes[idx] = PrefixNode()
            node = node.child_nodes[idx]
        node.complete_word = True

    def find_prefix(self, term):
        node = self.base
        for index, letter in enumerate(term):
            idx = ord(letter) - ord('a')
            if node.child_nodes[idx] is None:
                return term
            node = node.child_nodes[idx]
            if node.complete_word:
                return term[:index + 1]
        return term

class StringModifier:
    def replace_words(self, roots: List[str], line: str) -> str:
        terms = line.split()

        trie = PrefixTree()
        for root in roots:
            trie.add_word(root)

        for idx in range(len(terms)):
            terms[idx] = trie.find_prefix(terms[idx])

        return " ".join(terms)

This solution outlines an approach to replace words in a given sentence with the shortest possible prefixes contained in a specified list using a Python 3 program. The core of the solution involves implementing a Prefix Tree (Trie) to efficiently find and replace prefixed words.

  • The PrefixNode class initializes a node which may represent a complete word and manages links to child nodes. Each node potentially corresponds to one character of the alphabet, thus an array of size 26 is used.

  • The PrefixTree class oversees the operations of adding words and searching for prefixes. Adding a word involves iterating over each character, calculating its position in the alphabet, and creating new nodes as necessary. For finding prefixes, the process is similar; traverse nodes based on input word characters, and return the prefix if a complete word formation is detected along the traversal.

  • The StringModifier class leverages the PrefixTree to perform replacements in the input sentence:

    1. Split the input sentence into words.
    2. For each word, use the trie to find the shortest prefix from the provided list.
    3. Replace the word with its prefix as found.
    4. Finally, join the modified words back into a single string which represents the transformed sentence.

This setup efficiently manages word replacements, making good use of Trie's quick prefix lookup capabilities, which is vital for handling potentially large sets of prefix words and lengthy sentences.

Comments

No comments yet.