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.

Test Cases

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:

Solution

class TrieNode {

    boolean isEnd;
    TrieNode[] children;

    TrieNode() {
        isEnd = false;
        children = new TrieNode[26];
    }
}

class Trie {

    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode current = root;
        for (char c : word.toCharArray()) {
            if (current.children[c - 'a'] == null) {
                current.children[c - 'a'] = new TrieNode();
            }
            current = current.children[c - 'a'];
        }
        current.isEnd = true;
    }

    // Find the shortest root of the word in the trie
    public String shortestRoot(String word) {
        TrieNode current = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (current.children[c - 'a'] == null) {
                // There is not a corresponding root in the trie
                return word;
            }
            current = current.children[c - 'a'];
            if (current.isEnd) {
                return word.substring(0, i + 1);
            }
        }
        // There is not a corresponding root in the trie
        return word;
    }
}

class Solution {

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

        Trie dictTrie = new Trie();
        for (String word : dictionary) {
            dictTrie.insert(word);
        }

        // Replace each word in the sentence with the corresponding shortest root
        for (int word = 0; word < wordArray.length; word++) {
            wordArray[word] = dictTrie.shortestRoot(wordArray[word]);
        }

        return String.join(" ", wordArray);
    }
}
class Solution:
    def replaceWords(self, dictionary: List[str], sentence: str) -> str:
        root = Trie()
        for word in dictionary:
            root.insert(word)

        res, split = [], sentence.split(' ')
        for word in split:
            res.append(root.search(word))

        return ' '.join(res)

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str):
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.leaf = True

    def search(self, word: str) -> str:
        node = self.root
        for i in range(len(word)):
            c = word[i]
            if c not in node.children:
                return word
            node = node.children[c]
            if node.leaf:
                return word[:i+1]
        return word

class TrieNode:
    def __init__(self):
        self.children = {}
        self.leaf = False
Time Complexity: O(nm)
Space Complexity: O(d)