Replace Words - Practice Coding Problems

Replace Words - Problem

In English, we have a concept called root, which can be followed by some other word to form another longer word - let's call this word derivative. For example, when the root "help" is followed by the word "ful", we can form a derivative "helpful".

Given a dictionary consisting of many roots and a sentence consisting of words separated by spaces, replace all the derivatives in the sentence with the root forming it. If a derivative can be replaced by more than one root, replace it with the root that has the shortest length.

Return the sentence after the replacement.

Input & Output

Example 1 — Basic Root Replacement

$ Input: dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"

› Output: "the cat was rat by the bat"

💡 Note: "cattle" has prefix "cat", "rattled" has prefix "rat", "battery" has prefix "bat"

Example 2 — Shortest Root Priority

$ Input: dictionary = ["a","aa","aaa"], sentence = "aadsfasf absbs bbab cadsfafs"

› Output: "a a bbab cadsfafs"

💡 Note: "aadsfasf" and "absbs" both match "a" (shortest root), other words have no matching roots

Example 3 — No Matching Roots

$ Input: dictionary = ["catt","cat","bat","rat"], sentence = "the cattle was rattled by the battery"

› Output: "the cat was rat by the bat"

💡 Note: Even with "catt" in dictionary, "cat" is chosen as it's shorter and still matches "cattle"

Constraints

1 ≤ dictionary.length ≤ 1000
1 ≤ dictionary[i].length ≤ 100
1 ≤ sentence.length ≤ 10⁶
dictionary[i] and sentence consist of only lower-case letters

Visualization

Tap to expand

Understanding the Visualization

Input

Dictionary of roots and sentence with derivative words

Process

Find shortest root that is prefix of each word

Output

Sentence with derivatives replaced by roots

Key Takeaway

🎯 Key Insight: Use Trie for efficient prefix matching to find the shortest root that forms each derivative word

Asked in

G Google 25 a Amazon 18 M Microsoft 15 f Facebook 12

The key insight is to use prefix matching to find the shortest root that forms each derivative word. The optimal approach uses a Trie data structure for efficient prefix lookup, achieving O(m×k + n×k) time complexity where m is dictionary size, n is word count, and k is average string length.

Common Approaches

Approach	Time	Space	Notes
✓ Trie-Based Solution	O(m × k + n × k)	O(m × k)	Build a Trie from dictionary roots for efficient prefix matching
Brute Force	O(n × m × k)	O(1)	Check each word against all roots to find the shortest matching prefix
Hash Set Optimization	O(n × k²)	O(m × k)	Use hash set for O(1) root lookups while checking all prefixes of each word

Trie-Based Solution — Algorithm Steps

Step 1: Build Trie from all dictionary roots, marking end nodes
Step 2: For each word in sentence, traverse Trie with word characters
Step 3: Stop at first end node encountered (shortest root match)
Step 4: Replace word with matched root or keep original if no match

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Trie

Insert all dictionary roots into Trie structure

Traverse Path

Follow word characters down Trie paths

First End Node

Stop at first end node (shortest root match)

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct TrieNode {
    struct TrieNode* children[26];
    int isEnd;
} TrieNode;

TrieNode* createTrieNode() {
    TrieNode* node = malloc(sizeof(TrieNode));
    for (int i = 0; i < 26; i++) {
        node->children[i] = NULL;
    }
    node->isEnd = 0;
    return node;
}

void insertWord(TrieNode* root, char* word) {
    TrieNode* node = root;
    for (int i = 0; word[i]; i++) {
        int index = word[i] - 'a';
        if (node->children[index] == NULL) {
            node->children[index] = createTrieNode();
        }
        node = node->children[index];
    }
    node->isEnd = 1;
}

char* findRoot(TrieNode* root, char* word) {
    TrieNode* node = root;
    for (int i = 0; word[i]; i++) {
        int index = word[i] - 'a';
        if (node->children[index] == NULL) {
            return word;
        }
        node = node->children[index];
        if (node->isEnd) {
            char* result = malloc(i + 2);
            strncpy(result, word, i + 1);
            result[i + 1] = '\0';
            return result;
        }
    }
    return word;
}

char* solution(char** dictionary, int dictSize, char* sentence) {
    TrieNode* root = createTrieNode();
    
    for (int i = 0; i < dictSize; i++) {
        insertWord(root, dictionary[i]);
    }
    
    char* result = malloc(1000);
    result[0] = '\0';
    
    char* token = strtok(sentence, " ");
    int first = 1;
    
    while (token != NULL) {
        char* replacement = findRoot(root, token);
        
        if (!first) strcat(result, " ");
        strcat(result, replacement);
        first = 0;
        
        token = strtok(NULL, " ");
    }
    
    return result;
}

int main() {
    char line1[1000], line2[1000];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    
    line2[strcspn(line2, "\n")] = 0;
    
    char* dictionary[100];
    int dictSize = 0;
    char* start = strchr(line1, '"');
    while (start) {
        start++;
        char* end = strchr(start, '"');
        if (end) {
            *end = '\0';
            dictionary[dictSize] = malloc(strlen(start) + 1);
            strcpy(dictionary[dictSize], start);
            dictSize++;
            start = strchr(end + 1, '"');
        } else break;
    }
    
    char* sentence_copy = malloc(strlen(line2) + 1);
    strcpy(sentence_copy, line2);
    
    char* result = solution(dictionary, dictSize, sentence_copy);
    printf("%s\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m × k + n × k)

m roots × k length to build Trie + n words × k length to search

✓ Linear Growth

Space Complexity

O(m × k)

Trie nodes store all characters from m roots with average length k

✓ Linear Space

28.5K Views

Medium Frequency

~25 min Avg. Time

845 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Trie-Based Solution — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler