#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/pattern-22/trie/replace-words-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/pattern-22/trie/replace-words-implementation

Repovive

LeetCode 648 Replace Words - Implementation - Trie | Pattern 22: LeetCode Interview Patterns | Repovive

Repovive.

Pattern 22: LeetCode Interview Patterns24 sections · 736 units32h total

Open in Course

LeetCode 648 Replace Words - Implementation

The approach

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.