Given a dictionary of root words and a sentence, replace every word in the sentence with the shortest root word that is a prefix of that word. If a word has more than one matching root, use the shortest one. If a word has no matching root, keep it unchanged. Return the final sentence after all replacements.
Example 1
Input: dictionary = ["cat", "bat", "rat"], sentence = "the cattle was rattled by the battery"
Output: the cat was rat by the bat
Explanation: cattle becomes cat, rattled becomes rat, and battery becomes bat because those are the shortest matching roots.
Example 2
Input: dictionary = ["a", "b", "c"], sentence = "aadsfasf absbs bbab cadsfafs"
Output: a a b c
Explanation: Each word starts with one of the single-letter roots, so each word is replaced immediately by that shortest root.
Approach
The important observation is that the answer for each word depends only on its prefix, not on the whole dictionary. That matters because checking every root one by one for every sentence word would repeat a lot of work. A trie stores all roots by shared prefixes. So while reading a word from left to right, the search can stop as soon as the first complete root is found. That early stop is exactly what the problem wants, because the first root reached in trie traversal is automatically the shortest matching root.
Algorithm
First, insert every root word into a trie. This is done so common prefixes are stored together and prefix checking becomes fast for every sentence word.
While inserting a root, mark the last node as
end of word. This matters because only complete roots can replace a word, not just any matching character path.Split the sentence into individual words so each word can be processed separately and replaced independently.
For each word, start from the trie root and move character by character. This left-to-right walk matches the way prefixes are formed.
If the current character path does not exist in the trie, stop and keep the original word. This means no root in the dictionary can match this word anymore.
If a node marked as
end of wordis reached during traversal, stop immediately and return the prefix collected so far. This early return is important because the problem asks for the shortest matching root.Store the replaced word in the result list, then continue with the next sentence word until the full sentence is processed.
Join all processed words with spaces and return the final sentence
Key Points
Early stopping is the main idea here. The moment a complete root is found, checking deeper characters is unnecessary.
If one root is a prefix of another root, the shorter one must win. Trie traversal handles that naturally.
Words with no matching prefix must remain exactly the same.
Dry Run
Replace Words Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class TrieNode {public: vector<TrieNode*> children; bool isEndOfWord; // Creates one trie node with space for all lowercase letters. TrieNode() { // Start with no child paths from this node. children.assign(26, nullptr); // This node is not the end of a complete root yet. isEndOfWord = false; }};class Solution {private: // Inserts one root word into the trie. void insertRoot(TrieNode* root, const string& word) { // Start insertion from the trie root. TrieNode* node = root; for (char ch : word) { // Convert the current character into a trie index from 0 to 25. int index = ch - 'a'; // Create a new node only when this root needs a new path. if (node->children[index] == nullptr) { node->children[index] = new TrieNode(); } // Move forward so the next character continues from this node. node = node->children[index]; } // Mark the full root so searches know a valid replacement ends here. node->isEndOfWord = true; } // Finds the shortest root that can replace the given word. string findShortestRoot(TrieNode* root, const string& word) { // Start searching from the trie root. TrieNode* node = root; // Build the prefix step by step while moving through the trie. string prefix = ""; for (char ch : word) { // Convert the current character into a trie index from 0 to 25. int index = ch - 'a'; // If the path breaks, no root can match this word. if (node->children[index] == nullptr) { return word; } // Move to the next trie node for this character. node = node->children[index]; // Add the current character so the found root can be returned directly. prefix += ch; // Return immediately because the first full root is the shortest one. if (node->isEndOfWord) { return prefix; } } // If no earlier root was found, keep the original word. return word; }public: /* Replaces each word in the sentence with the shortest dictionary root that matches its prefix. */ string replaceWords(vector<string>& dictionary, string sentence) { // Create one trie that stores all root words. TrieNode* root = new TrieNode(); // Build the trie first so every sentence word can reuse the same prefix structure. for (const string& word : dictionary) { insertRoot(root, word); } // Read the sentence one word at a time. stringstream ss(sentence); // Stores the current word being processed from the sentence. string currentWord; // Stores the final words after replacement. vector<string> result; while (ss >> currentWord) { // Replace the current word only if a valid shortest root exists. result.push_back(findShortestRoot(root, currentWord)); } // Build the final sentence from the processed words. string answer = ""; for (int i = 0; i < (int)result.size(); i++) { // Add spaces only between words so the final sentence stays clean. if (i > 0) { answer += " "; } answer += result[i]; } return answer; }};// Driver code startsComplexity Analysis
Time Complexity: O(D + S), where D is the total number of characters in all dictionary roots and S is the total number of characters across all words in the sentence during trie search.
Space Complexity: O(D x 26) Where D represents the maximum number of Trie nodes needed to store all characters from the dictionary roots. Because each node statically allocates an array of 26 child pointers (for lowercase English letters) regardless of how many characters are actually attached to it, the memory footprint scales directly with D x 26.
Interview follow-up Questions
The search moves from left to right through the word. The first node that marks a complete root is the earliest possible valid prefix, so it must be the shortest matching root.
Be the first to add a comment.