Learn and practice the Graphs, Tries, and Custom Data Structures patterns to solve coding interview problems.

Educative-99 in Python: Accelerate Your Coding Interview Prep

Proficiency in advanced data structures is a marker of a highly experienced engineer, and interviewers use such questions to finetune how they grade candidates. This module teaches you the use of two advanced data structures—graphs and tries—to solve relatively complex problems. To solve problems with very specific requirements that may not be handled by standard data structures, we gain experience in the advanced skill of the design, implementation, and efficient use of custom data structures.

Advanced Data Structures

# Statement

In this problem, we are considering the words that are composed of a #key# prefix: A 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. #key# and a #key# postfix: A postfix is a formative element used at the end of a word. #key#. 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 \leq$ `dictionary.length` $\leq 1000$
* $1 \leq$ `dictionary[i].length` $\leq 100$ 
* `dictionary[i]` consists of only lowercase letters.
* $1 \leq$ `sentence.length` $\leq 10^3$
* The number of words in `sentence` is in the range $[1, 100]$.
* The length of each word in `sentence` is in the range $[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]$, and the length of a postfix can be $[0, 100]$.

# Examples

Replace Words

Statement