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

Solution: Replace Words

Explore how to replace words in a sentence by substituting postfixes with the shortest matching prefixes from a given dictionary. Learn to implement an efficient trie data structure to store dictionary prefixes and optimize search operations. Understand the step-by-step process to build the trie, search for prefixes, and modify the sentence accordingly. This lesson helps you apply trie-based patterns to improve time complexity from naive approaches, enabling more efficient string manipulation in coding interviews.

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
...