# Replace Words
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/replace-words)
Canonical: https://scaleengineer.com/dsa/problems/replace-words
**Data structures:** Array, Hash Table, String, Trie
---
## 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.

**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.

# Approaches
## Prefix Hashing with HashSet
This approach involves checking every prefix of each word in the sentence against a set of roots. We first store all the roots from the dictionary in a `HashSet` for quick lookups. Then, for each word in the sentence, we generate all its prefixes, from the shortest to the longest. The first prefix that we find in the `HashSet` is guaranteed to be the shortest root, so we use it as the replacement and move on to the next word.
**Time:** O(S_R + L + N * W^2), where `S_R` is the total characters in the dictionary, `L` is the sentence length, `N` is the number of words, and `W` is the max word length. Building the set is `O(S_R)`. For each of `N` words, generating and checking all prefixes takes `O(W^2)` time, making this the dominant and slowest part. · **Space:** O(S_R + L), where `S_R` is the sum of the lengths of all roots in the dictionary (for the `HashSet`) and `L` is the length of the sentence (for storing the split words and the result).
**Pros:** Conceptually simpler than a Trie.; Avoids iterating through the entire dictionary for each word.
**Cons:** Extremely inefficient due to the quadratic time complexity with respect to word length (`O(W^2)`).; This approach will likely result in a 'Time Limit Exceeded' error on platforms with strict time limits for the given constraints.
### Explanation
The core idea is to trade dictionary search time for prefix generation time. By putting all roots into a `HashSet`, we can check for the existence of a root in roughly constant time. However, to find the shortest root for a given word, we must check every single prefix of that word. We start with the prefix of length 1, check if it's in the set. If not, we check the prefix of length 2, and so on. The first time we find a prefix that is in the set, we know it must be the shortest possible root for that word, so we can stop and use it as the replacement. If we check all prefixes of a word and find no match, the word remains unchanged.

```java
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public String replaceWords(List<String> dictionary, String sentence) {
        Set<String> rootSet = new HashSet<>(dictionary);
        String[] words = sentence.split(" ");
        StringBuilder result = new StringBuilder();

        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            String replacement = word;
            // Iterate through all prefixes of the word
            for (int j = 1; j <= word.length(); j++) {
                String prefix = word.substring(0, j);
                if (rootSet.contains(prefix)) {
                    // Found the shortest root, no need to check longer prefixes
                    replacement = prefix;
                    break; 
                }
            }
            result.append(replacement);
            if (i < words.length - 1) {
                result.append(" ");
            }
        }
        return result.toString();
    }
}
```
### Algorithm
- Create a `HashSet` and add all roots from the `dictionary` to it for O(1) average time lookups.
- Split the `sentence` into an array of `words`.
- For each `word` in the sentence:
  - Iterate through all possible prefixes of the `word`, from length 1 up to the word's full length.
  - For each `prefix`, check if it exists in the `HashSet`.
  - The first prefix found will be the shortest root. Replace the word with this prefix and break the inner loop to proceed to the next word.
  - If no prefix is found in the set, the original word is kept.
- Join the modified words back into a sentence.

## Brute Force Iteration
This is a straightforward brute-force approach where for each word in the sentence, we iterate through the entire dictionary to find a matching root. To handle the requirement of using the shortest root, we simply keep track of the shortest valid root found so far for each word.
**Time:** O(L + N * D * R), where `L` is the sentence length, `N` is the number of words, `D` is the dictionary size, and `R` is the average root length. Splitting the sentence takes `O(L)`. The main work is in the nested loops, which run `N * D` times, with the `startsWith` check taking `O(R)` time. · **Space:** O(L), where `L` is the length of the sentence. This space is used to store the array of words and the final result string.
**Pros:** Easy to understand and implement.; Requires minimal auxiliary space.
**Cons:** Very inefficient for large inputs due to the nested loops.; The time complexity `O(N * D * R)` will be too high for the given constraints and will likely time out.
### Explanation
This method directly translates the problem statement into code. We first break the sentence down into its constituent words. Then, for every single word, we perform a linear scan through the entire dictionary. For each root in the dictionary, we check if our current word starts with it. If it does, we compare its length with the shortest root we've found so far for this word. If the new root is shorter, we update our choice. After checking all possible roots against a word, we replace the word with the shortest root we found. If no root was a prefix, the word remains unchanged as it was its own initial 'shortest root'.

```java
import java.util.List;

class Solution {
    public String replaceWords(List<String> dictionary, String sentence) {
        String[] words = sentence.split(" ");
        
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            String shortestRoot = word;
            for (String root : dictionary) {
                if (word.startsWith(root)) {
                    if (root.length() < shortestRoot.length()) {
                        shortestRoot = root;
                    }
                }
            }
            words[i] = shortestRoot;
        }
        
        return String.join(" ", words);
    }
}
```
### Algorithm
- Split the `sentence` into an array of `words`.
- Iterate through each `word` in the `words` array.
- For each `word`, initialize a `replacement` variable to be the word itself.
- Start a nested loop to iterate through every `root` in the `dictionary`.
- Inside the nested loop, check if the current `word` starts with the current `root`.
- If it does, and if this `root` is shorter than the current `replacement`, update `replacement` to this `root`.
- After checking all roots, the `replacement` variable will hold the shortest possible root (or the original word).
- Update the word in the array with the `replacement`.
- Finally, join the words in the array back into a single string.

## Optimal Approach with Trie (Prefix Tree)
The most efficient way to solve this problem is by using a Trie (also known as a prefix tree). A Trie is a tree-like data structure perfect for problems involving prefixes. We first build a Trie by inserting all the roots from the dictionary. Then, for each word in the sentence, we traverse the Trie to find the shortest prefix of that word that corresponds to a root in the dictionary.
**Time:** O(S_R + L), where `S_R` is the sum of all characters in the dictionary and `L` is the length of the sentence. Building the Trie takes `O(S_R)`. Processing the sentence takes `O(L)` because each character is visited once during the Trie traversal. · **Space:** O(S_R + L), where `S_R` is the sum of lengths of all roots (for the Trie) and `L` is the sentence length (for the split words and result).
**Pros:** Highly efficient with linear time complexity relative to the total input size.; The optimal solution for this problem, easily handling the given constraints.
**Cons:** Requires implementing a custom Trie data structure, which adds complexity to the code compared to using built-in collections.
### Explanation
A Trie is tailor-made for prefix-based searches. We begin by constructing the Trie. Each node represents a character, and a path from the root to a node represents a prefix. We insert all dictionary roots into this Trie. We modify the Trie nodes to hold the actual root word at the node where the root terminates. This is a key optimization.

After building the Trie, we process the sentence. For each word, we walk down the Trie, following the path given by the word's characters. As we traverse, if we land on a node that contains a stored root word, we know we've found a valid prefix. Because we are processing the word from its beginning, the *first* such root we encounter is guaranteed to be the shortest one. We can immediately use this root as the replacement and move to the next word in the sentence. If our traversal is blocked (no child for a character) or finishes without finding a root, the word is not a derivative and is left as is.

```java
import java.util.List;

class Solution {
    class TrieNode {
        TrieNode[] children = new TrieNode[26];
        String word = null; // Store the full word at the end node
    }

    public String replaceWords(List<String> dictionary, String sentence) {
        TrieNode root = new TrieNode();
        // 1. Build the Trie with all roots
        for (String word : dictionary) {
            TrieNode curr = root;
            for (char c : word.toCharArray()) {
                if (curr.children[c - 'a'] == null) {
                    curr.children[c - 'a'] = new TrieNode();
                }
                curr = curr.children[c - 'a'];
            }
            curr.word = word;
        }

        String[] words = sentence.split(" ");
        StringBuilder result = new StringBuilder();

        // 2. Replace words in the sentence by searching the Trie
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            TrieNode curr = root;
            String replacement = word; // Default to original word
            
            for (char c : word.toCharArray()) {
                if (curr.children[c - 'a'] == null || curr.word != null) {
                    // Path broken or a shorter root has already been found
                    break;
                }
                curr = curr.children[c - 'a'];
                if (curr.word != null) {
                    // Found a root prefix. It's the shortest one.
                    replacement = curr.word;
                    break;
                }
            }
            result.append(replacement);
            if (i < words.length - 1) {
                result.append(" ");
            }
        }
        
        return result.toString();
    }
}
```
### Algorithm
- Define a `TrieNode` class containing an array for child nodes and a field to mark the end of a word (e.g., a string to store the root).
- Build a Trie by inserting every `root` from the `dictionary`.
- Split the `sentence` into words.
- For each `word` in the sentence:
  - Traverse the Trie from the root, character by character, following the path corresponding to the `word`.
  - During traversal, if you reach a node that marks the end of a root, you have found the shortest possible root prefix. Record this root and break the traversal for the current word.
  - If the path breaks (a character has no corresponding child node), it means no root matches this prefix. Stop and keep the original word.
  - If you traverse all characters of the word without finding a root, keep the original word.
- Replace the original word with the found root (if any).
- Join the processed words to form the final sentence.

# Solutions
### Java

```java
class Trie { private Trie [] children = new Trie [ 26 ]; private int ref = - 1 ; public void insert ( String w , int i ) { Trie node = this ; for ( int j = 0 ; j < w . length (); ++ j ) { int idx = w . charAt ( j ) - 'a' ; if ( node . children [ idx ] == null ) { node . children [ idx ] = new Trie (); } node = node . children [ idx ]; } node . ref = i ; } public int search ( String w ) { Trie node = this ; for ( int j = 0 ; j < w . length (); ++ j ) { int idx = w . charAt ( j ) - 'a' ; if ( node . children [ idx ] == null ) { return - 1 ; } node = node . children [ idx ]; if ( node . ref != - 1 ) { return node . ref ; } } return - 1 ; } } class Solution { public String replaceWords ( List < String > dictionary , String sentence ) { Trie trie = new Trie (); for ( int i = 0 ; i < dictionary . size (); ++ i ) { trie . insert ( dictionary . get ( i ), i ); } List < String > ans = new ArrayList <>(); for ( String w : sentence . split ( "\\s" )) { int idx = trie . search ( w ); ans . add ( idx == - 1 ? w : dictionary . get ( idx )); } return String . join ( " " , ans ); } }
```

### CPP

```cpp
class Trie { private: Trie * children [ 26 ]; int ref ; public: Trie () : ref ( - 1 ) { memset ( children , 0 , sizeof ( children )); } void insert ( const string & w , int i ) { Trie * node = this ; for ( auto & c : w ) { int idx = c - 'a' ; if ( ! node -> children [ idx ]) { node -> children [ idx ] = new Trie (); } node = node -> children [ idx ]; } node -> ref = i ; } int search ( const string & w ) { Trie * node = this ; for ( auto & c : w ) { int idx = c - 'a' ; if ( ! node -> children [ idx ]) { return - 1 ; } node = node -> children [ idx ]; if ( node -> ref != - 1 ) { return node -> ref ; } } return - 1 ; } }; class Solution { public: string replaceWords ( vector < string >& dictionary , string sentence ) { Trie * trie = new Trie (); for ( int i = 0 ; i < dictionary . size (); ++ i ) { trie -> insert ( dictionary [ i ], i ); } stringstream ss ( sentence ); string w ; string ans ; while ( ss >> w ) { int idx = trie -> search ( w ); ans += ( idx == - 1 ? w : dictionary [ idx ]) + " " ; } ans . pop_back (); return ans ; } };
```

### Python

```python
class Trie : def __init__ ( self ): self . children : List [ Trie | None ] = [ None ] * 26 self . ref : int = - 1 def insert ( self , w : str , i : int ): node = self for c in w : idx = ord ( c ) - ord ( "a" ) if node . children [ idx ] is None : node . children [ idx ] = Trie () node = node . children [ idx ] node . ref = i def search ( self , w : str ) -> int : node = self for c in w : idx = ord ( c ) - ord ( "a" ) if node . children [ idx ] is None : return - 1 node = node . children [ idx ] if node . ref != - 1 : return node . ref return - 1 class Solution : def replaceWords ( self , dictionary : List [ str ], sentence : str ) -> str : trie = Trie () for i , w in enumerate ( dictionary ): trie . insert ( w , i ) ans = [] for w in sentence . split (): idx = trie . search ( w ) ans . append ( dictionary [ idx ] if idx != - 1 else w ) return " " . join ( ans )
```