Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns

Replace Words

Explore how to use trie data structures to replace postfixes in a sentence with their shortest matching prefixes from a given dictionary. This lesson teaches you to efficiently identify and substitute word parts, handling multiple prefix matches and returning modified sentences accordingly.

We'll cover the following...

Statement

In this problem, we are considering the words that are composed of a prefixA prefix is a formative element (the smallest meaningful constituent of a linguistic expression) used at the very beginning of a word. For example, ‘un’, ‘dis’, ‘anti’, etc. and a postfixA postfix is a formative element used at the end of a word.. For example, if we append a postfix “happy” to a prefix “un”, it forms the word “unhappy”. Similarly, “disagree” is formed from a prefix, “dis” followed by a postfix, “agree”.

You’re given a dictionary, dictionary, consisting of prefixes, and a sentence, sentence, which has words separated by spaces only. Your task is to replace the postfix in sentence with their prefixes given in dictionary (if found) and return the modified sentence.

A couple of points to keep in mind:

  • If a postfix in the sentence matches more than one prefix in the dictionary, replace it with the prefix that has the shortest length. For example, if we have the sentence “iphone is amazing”, and the dictionary {“i”, “ip”, “hone”}, then the word “iphone” has two prefixes in the dictionary “i” and “ip”, but we will replace it with the one that is shorter among the two, that is, “i”.

  • If there is no root word against any word in the sentence, leave it unchanged.

Constraints:

  • 1≤1 \leq dictionary.length ≤1000\leq 1000
  • 1≤1 \leq dictionary[i].length ≤100\leq 100
  • dictionary[i] consists of only lowercase letters.
  • 1≤1 \leq sentence.length ≤103\leq 10^3
  • The number of words in sentence is in the range [1,100][1, 100].
  • The length of each word in sentence is in the range [1,100][1, 100].
  • Two consecutive words in sentence should be separated by exactly one space.
  • All words in sentence are lowercase.
  • For a word in sentence, the length of a prefix can be [1,100][1, 100], and the length of a postfix can be [0,100][0, 100].

Examples

canvasAnimation-image
1 / 3

Understand the problem

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Technical Quiz
1.

Choose the correct output given the following inputs.

sentence = “when life gives you lemons make lemonade”
dictionary = {“li”, “gi”, “lem”, “m”, “l”}

A.

“when li gi you lem make l”

B.

“when l gi you lem m lem”

C.

“when l gi you l make l”

D.

“when l gi you l m l”

1 / 3

Figure it out!

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Sequence - Vertical
Drag and drop the cards to rearrange them in the correct sequence.
1
2
3
4

Try it yourself

Implement your solution in main.java in the following coding playground. You’ll need the provided supporting code to implement your solution.

Java
usercode > Main.java
import java.util.*;



public class Main {

   public static String replaceWords(String sentence, List<String> dictionary) {



      // Replace this placeholder return statement with your code

      return "";

   }

}
Replace Words