Replace Words Solution

Build trie of roots, then find shortest match for each word:

def replaceWords(dictionary, sentence):
    # Build trie
    root = TrieNode()
    for word in dictionary:
        node = root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.isEnd = True

    # Find shortest root for each word
    def findRoot(word):
        node = root
        for i, c in enumerate(word):
            if c not in node.children:
                return word
            node = node.children[c]
            if node.isEnd:
                return word[:i+1]
        return word

    words = sentence.split()
    return " ".join(findRoot(w) for w in words)

The key: return as soon as you hit a word ending. You get the shortest matching root.

Time: $O(D + S)$ where $D$ is total dictionary size and $S$ is sentence length.