LeetCode 648 Replace Words - Implementation

Build trie from roots, find shortest prefix for each word.

function replaceWords(dictionary, sentence): trie = {} for root in dictionary: node = trie for char in root: if char not in node: node[char] = {} node = node[char] node['$'] = root

def findRoot(word):
    node = trie
    for char in word:
        if '$' in node:
            return node['$']
        if char not in node:
            return word
        node = node[char]
    return node.get('$', word)

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

$O(n + m)$ time and space.