Replace Words — Trie Shortest Prefix Replacement

Problem

Given a dictionary of roots, replace each word in a sentence with its shortest root. If no root, keep original.

Solutions

Python

class Solution:
    def replaceWords(self, dictionary: list[str], sentence: str) -> str:
        root={}
        for word in dictionary:
            node=root
            for c in word:
                if c not in node: node[c]={}
                node=node[c]
            node['#']=word
        def replace(word):
            node=root
            for c in word:
                if c not in node: return word
                node=node[c]
                if '#' in node: return node['#']
            return word
        return ' '.join(replace(w) for w in sentence.split())

Complexity

Time: O(total chars) build + O(sentence words * max root len) query