LC648. Replace Words

Approach 1: Prefix Trie

class Trie:
    def __init__(self, words):
        self.root = {
            "value": "",
            "terminal": False,
            "children": {}
        }
        self.buildTrie(words)
    
    def buildTrie(self, words):
        for word in words:
            self.addToTrie(word)
 
    def addToTrie(self, word):
        curr = self.root
        for c in word:
            curr["children"][c] = curr["children"].get(c, {
                    "value": c,
                    "terminal": False,
                    "children": {}
                })
 
            curr = curr["children"][c]
        
        curr["terminal"] = True
 
    def findShortestPrefix(self, word):
        curr = self.root
        prefix = ""
        for c in word:
            node = curr["children"].get(c, None)
            if node is None:
                return word
 
            prefix += node["value"]
            
            if node["terminal"]:
                return prefix
            
            curr = node
 
        return prefix
 
class Solution:
    def replaceWords(self, dictionary: List[str], sentence: str) -> str:
        trie = Trie(dictionary)
 
        words = sentence.split(" ")
 
        res = [""] * len(words)
        for i in range(len(words)):
            res[i] = trie.findShortestPrefix(words[i])
        
        return " ".join(res)

Complexity

Parameters:

1. $d$ is number of words in dictionary
2. $s$ is number of words in sentence
3. $w$ is average length of a word

Time: $O(d\cdot w+s\cdot w)$
Space: $O(d\cdot w+s\cdot w)$

Other Languages