Replace with roots
For each word, walk until the first end marker: that prefix is its shortest known root. About 10 minutes.
Stop at the first match
This is nearly the same walk as finding the longest known prefix, but with the opposite goal. Stop and use the very first end marker you meet, because that is the shortest root.
Think of a nickname: you'd use the shortest known form. If the walk never crosses an end marker, this word has no known root and stays as it is.
for i, c in enumerate(word):
if "$" in node:
return word[:i] # a word ends
node = node[c]- result
- [cat]
"cattle": c, a, t, and t is an end. Stop at the first end: the shortest root. Replace with "cat".
One word at a time
Build the trie from the dictionary once. Then walk each word of the sentence on its own through that same trie, and replace it if a root is found.
It is like a single spell-checker dictionary used for every word of a long message: you don't rebuild it for each word.
dictionary = ["cat", "ca"], and the sentence has the word "catalog". What replaces it?
- A"ca"
- B"cat"
Show the answer
"ca". Walking "catalog", the node for "c" then "a" is already marked as an end (from "ca"): that's the first, shortest match.
Replace with roots
dictionary is a list of lowercase root words, and sentence is a list of lowercase words. For each word in sentence, if some root in dictionary is a prefix of it, replace it with the shortest such root; otherwise leave it unchanged. Return the resulting list, in the same order as sentence.
dictionary = ["cat", "bat", "rat"], sentence = ["cattle", "battery", "ratio", "war"] → ["cat", "bat", "rat", "war"]
0 ≤ dictionary.length, sentence.length ≤ 1,000 · 1 ≤ dictionary[i].length, sentence[i].length ≤ 30 · every word is lowercase a-z