Course4all
Join us on telegram
Home/dsa/Trie/Replace Words

Replace Words

Master this topic with zero to advance depth.

Replace Words

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 successor. For example, when the root "an" is followed by the successor word "other", we can form a new word "another".\n\nGiven a dictionary consisting of many roots and a sentence consisting of words separated by spaces, replace all the successors in the sentence with the root forming it. If a successor can be replaced by more than one root, replace it with the root that has the shortest length.

Medium

Examples

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

Level I: HashSet of Roots

Intuition

Store all roots in a HashSet. For each word in the sentence, check every possible prefix (starting from length 1) in the HashSet. Return the first match found.

⏱ O(SentenceLength * WordLength^2)💾 O(DictionaryLength * RootLength)

Detailed Dry Run

Word: 'cattle'. Check 'c', 'ca', 'cat'. 'cat' is in HashSet. Replace 'cattle' with 'cat'.

java
import java.util.*;
class Solution {
    public String replaceWords(List<String> roots, String sentence) {
        Set<String> set = new HashSet<>(roots);
        StringBuilder res = new StringBuilder();
        for(String word : sentence.split(" ")) {
            String prefix = "";
            for(int i=1; i<=word.length(); i++) {
                prefix = word.substring(0, i);
                if(set.contains(prefix)) break;
            }
            if(res.length()>0) res.append(" ");
            res.append(prefix);
        }
        return res.toString();
    }
}
Approach 2

Level III: Trie (Optimal)

Intuition

Build a Trie from the roots. For each word in the sentence, traverse the Trie. The first isEndOfWord node encountered provides the shortest root.

⏱ O(DictionaryLength * RootLength + SentenceLength)💾 O(DictionaryLength * RootLength)

Detailed Dry Run

Trie: root -> c -> a -> t (end). Word: 'cattle'. Traverse c -> a -> t (found end). Return 'cat'.

java
class Solution {
    class Node { Node[] children = new Node[26]; boolean isEnd; }
    Node root = new Node();
    public String replaceWords(List<String> dictionary, String sentence) {
        for (String s : dictionary) { Node curr = root; for (char c : s.toCharArray()) { int i = c - 'a'; if (curr.children[i] == null) curr.children[i] = new Node(); curr = curr.children[i]; } curr.isEnd = true; }
        StringBuilder res = new StringBuilder();
        for (String word : sentence.split(" ")) {
            if (res.length() > 0) res.append(" ");
            Node curr = root; StringBuilder prefix = new StringBuilder();
            for (char c : word.toCharArray()) {
                int i = c - 'a'; if (curr.children[i] == null || curr.isEnd) break;
                prefix.append(c); curr = curr.children[i];
            }
            res.append(curr.isEnd ? prefix.toString() : word);
        }
        return res.toString();
    }
}
← Previous QuestionMap Sum Pairs
Next Question →Word Search II