In English, we have a concept called
root, which can be followed by some other words to form another longer word - let's call this word
successor. For example, the root
an, followed by
other, which can form another word
Now, given a dictionary consisting of many roots and a sentence. You need to replace all the
successor in the sentence with the
root forming it. If a
successor has many
roots can form it, replace it with the root with the shortest length.
You need to output the sentence after the replacement.
Input: dict = ["cat", "bat", "rat"] sentence = "the cattle was rattled by the battery" Output: "the cat was rat by the bat"
For each word in the sentence, we\'ll look at successive prefixes and see if we saw them before.\n
Store all the
roots in a Set structure. Then for each word, look at successive prefixes of that word. If you find a prefix that is a root, replace the word with that prefix. Otherwise, the prefix will just be the word itself, and we should add that to the final sentence answer.
Time Complexity: where is the length of the -th word. We might check every prefix, the -th of which is work.\n
Space Complexity: where is the length of our sentence; the space used by
Intuition and Algorithm\n
Put all the roots in a trie (prefix tree). Then for any query word, we can find the smallest root that was a prefix in linear time.\n\n
Time Complexity: where is the length of the
sentence. Every query of a word is in linear time.
Space Complexity: , the size of our trie.\n
Analysis written by: @awice.\n