Problem statement

https://leetcode.com/problems/replace-words/

Solution

Best complexity solution is to put all our dictionary to trie, then we just traverse our string and stop either when word is ended or we found ending node in our Trie.

Complexity

Time and space complexity will be O(m + n), where m is total length of all words in dictionary.

Code

class TrieNode:
    def __init__(self):
        self.children = {}
        self.end_word = None

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word): #None
        node = self.root
        for symbol in word:
            node = node.children.setdefault(symbol, TrieNode())
        node.end_word = word
        
    def find(self, word):
        node = self.root
        for l in word:
            if l not in node.children or node.end_word: break
            node = node.children[l]
        return node.end_word if node.end_word else word
        
class Solution:
    def replaceWords(self, dictionary, sentence):
        trie = Trie()
        for word in dictionary:
            trie.insert(word)
            
        return " ".join(trie.find(word) for word in sentence.split())

Remark

There is also solution where we put all our dictionary to set. Let words have $w_1,\dots w_k$ be lengths of words in split string, then we have time complexity $O(\sum\limits_{i=1}^k w_k^2)$ and space complexity $O(\sum\limits_{i=1}^k w_k) = O(n)$. It sound like big number, but it is quite fast in python.