Replace Words
Medium · Tries · Array · Hash Table · String · Trie
Problem
A root is a word that can be extended into longer words. For example, the root "help" followed by "ful" forms "helpful".
You are given a list of roots dictionary and a string sentence of words separated by single spaces. Replace every word that has a root from the dictionary as a prefix with that root. If several roots are prefixes of a word, use the shortest. Words with no root stay unchanged.
Return the sentence after all replacements.
Examples
Input: dictionary = ["sun","sunf","rain"], sentence = "sunflowers need rainy days" Output: "sun need rain days"
"sunflowers" starts with both "sun" and "sunf"; the shorter one wins. "rainy" becomes "rain".
Input: dictionary = ["x","y"], sentence = "yes xray zed" Output: "y x zed"
"zed" has no root, so it stays.
Input: dictionary = ["cat","catalog"], sentence = "cats catalogs ca" Output: "cat cat ca"
"cat" is the shortest root of the first two words; "ca" is shorter than every root and stays.
Constraints
- 1 <= len(dictionary) <= 1000
- 1 <= len(dictionary[i]) <= 100
- 1 <= len(sentence) <= 10^6
- dictionary[i] and the words of sentence are lowercase letters; words are separated by single spaces, with no leading or trailing space
- Every word of sentence has 1 to 1000 letters
Approaches
- Baseline: try every root on every word — time O(W · D · L), space O(1) beyond the answer
Follow-up
What if the longest root should win, or roots matched the end of words instead of the start? The use cases change one detail of the walk each.
Start free on Cariara · Coding problems · System design studio
