Build trie of roots, then find shortest match for each word:
def replaceWords(dictionary, sentence):
# Build trie
root = TrieNode()
for word in dictionary:
node = root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.isEnd = True
# Find shortest root for each word
def findRoot(word):
node = root
for i, c in enumerate(word):
if c not in node.children:
return word
node = node.children[c]
if node.isEnd:
return word[:i+1]
return word
words = sentence.split()
return " ".join(findRoot(w) for w in words)
The key: return as soon as you hit a word ending. You get the shortest matching root.
Time: where is total dictionary size and is sentence length.