Replace Words
A text shortener swaps words for roots. The dictionary lists the roots. A word that starts with one or more of them is replaced by the SHORTEST root that starts it, and a word that no root starts stays as it is. Keep the words in their order with one space between them, and return the new sentence. Limits: 1 <= dictionary.length <= 50000, each root has 1 to 100 lowercase letters, and roots may repeat. The sentence has up to 500000 characters: lowercase words separated by single spaces, with no space at either end. Think about: how can you ask "does some root start this word?" without checking the whole dictionary for every word? Example: dictionary = ["tea", "te", "pot"], sentence = "teapot tender potted tame" teapot is started by te and tea, and the shorter te wins tender is started by te, potted by pot, and nothing starts tame Return "te te pot tame".
You're shortening a sentence by swapping each word for the shortest dictionary root that starts it. Looping over every root for every word is fine on a small input and quietly melts on a big one, which is exactly what interviewers want to see you notice. The classic trap is grabbing the first root that fits instead of the shortest. Expect up to 50,000 roots and a sentence of up to 500,000 characters.
Examples
You write
replace_words(dictionary: List[str], sentence: str)
Example 1
- Input
- dictionary = ["tea","te","pot"], sentence = "teapot tender potted tame"
- returns
- "te te pot tame"
Example 2
- Input
- dictionary = ["go"], sentence = "go"
- returns
- "go"
Save this for your laptop
The editor and Run need a bigger screen. The link opens Replace Words ready to code. It is free, and the editor needs no account.
The pattern behind it
Strings
I reach for it when
- The input is text and the answer is a count, a substring or a new string.
- You need to compare, reverse or rebuild characters.
Say this before you type. Say which array pattern the string is hiding before you touch a character.
All 49 Strings problemsArrays & Hashing
I reach for it when
- You catch yourself scanning the array again for every element.
- The problem asks about duplicates, pairs, counts or groups.
Say this before you type. Say what the key is and what the value remembers, before you write the loop.
All 126 Arrays & Hashing problems
Meet Coco
Coco is an AI study partner, not a person. She listens while you explain your code, asks what a line does and never hands you the fix. Sign in free to type with Coco, up to a daily limit, and to talk with her for one hour. After that, talking comes with the $79 pack. Anyone can open the editor and run their code.