648. Replace Words

Replace Words (LeetCode 648) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Design Patterns pattern, in the Tries subpattern.

How to solve Replace Words

Replace Words is a Trie Implementation problem, part of Design Patterns. Implement Trie data structure for prefix-based operations and autocomplete systems.

Work towards the solution in these steps:

1. Think about a data structure that can efficiently store a collection of prefixes and enable quick prefix lookups for words in the sentence.
2. A Trie (prefix tree) is well-suited for this problem as it can help you find the shortest root prefix for any given word efficiently.
3. Build a Trie from all the root words in the dictionary, then for each word in the sentence, traverse the Trie character by character to find the shortest matching root prefix.

The reference solution runs in O(n) time and O(t) space.

The Replace Words solution and editorial walks through the full approach with reference code.

Problem statement

In English, we have a concept called root, which can be followed by some other word to form another longer word - let's call this word successor. For example, when the root "an" is followed by the successor word "other", we can form a new word "another".

Given a dictionary consisting of many roots and a sentence consisting of words separated by spaces, replace all the successors in the sentence with the root forming it. If a successor can be replaced by more than one root, replace it with the root that has the shortest length.

Return the sentence after the replacement.

Example 1: Input: dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery" Output: "the cat was rat by the bat"

Example 2: Input: dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs" Output: "a a b c"

Example 3: Input: dictionary = ["a", "aa", "aaa", "aaaa"], sentence = "a aa a aaaa aaa aaa aaa aaaaaa bbb baba ababa" Output: "a a a a a a a a bbb baba a"

Example 4: Input: dictionary = ["catt","cat","bat","rat"], sentence = "the cattle was rattled by the battery" Output: "the cat was rat by the bat"

Example 5: Input: dictionary = ["ac","ab"], sentence = "it is abnormal that this solution is accepted" Output: "it is ab that this solution is ac"

Constraints: 1 <= dictionary.length <= 1000 1 <= dictionary[i].length <= 100 dictionary[i] consists of only lower-case letters.

1 <= sentence.length <= 10^6 sentence consists of only lower-case letters and spaces.

The number of words in sentence is in the range [1, 1000] The length of each word in sentence is in the range [1, 1000] Each two consecutive words in sentence will be separated by exactly one space.

sentence does not have leading or trailing spaces.

Topics and companies

Topics: Hash Table, Trie.

Reported in interviews at Uber.

How to practise Replace Words on Thita.ai

Starter code is provided in C, C#, C++, dart, elixir, erlang, Go, Java, JavaScript, Kotlin, PHP, Python, python3, racket, Ruby, Rust, Scala, Swift and TypeScript. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(t) space.

Open Replace Words in the code editor, or read the Replace Words editorial for a worked solution with its approach and complexity analysis.

Where Replace Words sits in the DSA pattern sheet

• Design Patterns pattern guide
• Tries subpattern
• The full DSA patterns sheet

Problems related to Replace Words

Other problems that use the same Tries and Design Patterns techniques:

• Design Add and Search Words Data Structure — Medium, same subpattern
• Extra Characters in a String — Medium, same subpattern
• Implement Trie (Prefix Tree) — Medium, same subpattern
• Longest Word in Dictionary — Easy, same subpattern
• Prefix and Suffix Search — Hard, same subpattern
• Word Squares — Hard, same subpattern

Replace Words FAQ