Replace Words With Roots
Problem
You are given a list of root words and a sentence of space-separated words. Replace every word in the sentence that begins with one of the roots by that root. When several roots match the same word, use the shortest one. Words matching no root are left alone.
Examples
Input: roots = ["cat", "bat", "rat"], sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"
Why: each replaced word starts with a stored rootInput: roots = ["a", "aa"], sentence = "aaa aab"
Output: "a a"
Why: the shortest matching root wins, so "aa" never appliesInput: roots = ["xy"], sentence = "x"
Output: "x"
Why: edge case, the word is shorter than any rootHints
0 / 3
Testing every root against every word repeats work whenever two roots share a beginning. Store the roots once, in a shape that answers 'does any root end here?'
A trie lets you walk a word character by character while the roots are consumed in parallel.
For each word, descend from the trie root one character at a time. The first node you reach that is marked as a root end gives the shortest match, so stop there. If you fall off the trie first, the word has no root.
Solution
Insert every root into a trie with a sentinel marking its final node. Then walk each sentence word down the trie: the first sentinel encountered is by construction the shortest matching root, so the scan stops immediately. Falling off the trie means no root matches. Building costs O(total root length); each word costs at most its own length. Total time is O(R + S) over root and sentence characters, with O(R) space.
def replace_words(roots, sentence):
trie = {}
for r in roots:
node = trie
for ch in r:
node = node.setdefault(ch, {})
node["$"] = True # a root ends here
out = []
for word in sentence.split():
node, cut = trie, None
for i, ch in enumerate(word):
if ch not in node:
break # fell off: no root matches
node = node[ch]
if "$" in node:
cut = i + 1 # first hit is the shortest root
break
out.append(word[:cut] if cut else word)
return " ".join(out)
print(replace_words(["cat", "bat", "rat"], "the cattle was rattled by the battery"))
# -> the cat was rat by the bat
print(replace_words(["a", "aa"], "aaa aab"), "|", replace_words(["xy"], "x")) # -> a a | xStuck on the idea rather than the code? Prefix Search covers it.