Advanced Data Structures: Implementing Tries in C++ and Java/

...

/

Prefix Replacement

Prefix Replacement

Solve a medium-level problem of prefix replacement in a sentence using tries.

We'll cover the following...

Problem statement

We can append some other words to a prefix to frame new words. For example, the prefix re can be followed by words start and cap to form words restart or recap.

Given a list consisting of multiple prefixes and a sentence, replace all the words in the sentence with the prefix forming it. If a word can be replaced by more than one prefix, replace it with the prefix that has the shortest length.

Return the modified sentence after the replacement.

Example 1

Sample Input

prefixes: ["cat", "sat", "mat"]
sentence: "the cattle sat on the mattress"

Sample output

"the cat sat on the mat"

Explanation

For the sentence "the cattle sat on the mattress", the words "cattle", "sat" and "mattress" are replaced by their respective matching prefixes "cat", "sat" and "mat", while the other words remain the same.

Example 2

Sample Input

prefixes: ["we", "west", "week"]
sentence = "we love to watch western movies on weekend"

Sample output

"we love to watch we movies on we"

Explanation

For the sentence "we love to watch western movies on weekend", the word "we" is replaced by it’s shortest matching prefix "we". Similarly, the words "western" and "weekend" are also replaced by their shortest matching prefix "we" instead of the prefixes "west" and "week" respectively.

Try it yourself

Try to solve the problem yourself before reading the solution.

#include <iostream>

#include <vector>

using namespace std;



string replaceWords(vector<string> dictionary, string sentence) {

    // your code goes here

    return "";

}
Solve prefix replacement in C++

Intuition

For every word of the given sentence, we need to check if it has a valid prefix root present in the prefixes list. Using the brute-force approach would involve comparing each word of the sentence with each word of the prefixes list to check if there is a valid prefix root present for the given word. This procedure would incur a high time complexity.

The problem is related to strings and prefix search. Tries are an efficient data structure for prefix search–related problems. We can store the words of the prefixes list in a trie and leverage the prefix searching capability of finding valid prefix roots for all the words of the given sentence.

Algorithm

The summary of the algorithm is given below.

Step 1: Insertion of prefix words in a trie

Insert all the words of the prefixes list into a trie. Set the value of isEndOfWord as true for the trie node associated with the last character of the prefix word.

Step 2: Finding prefix roots and replacing sentence words

Iterate through every word of the given sentence and perform the ...

Create a free account to view this lesson.

By signing up, you agree to Educative's Terms of Service and Privacy Policy