Solution: Replace Words

Let's solve the Replace Words problem using the Trie pattern.

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

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

This problem requires us to observe the leading characters (prefixes) of words in a sentence that can be replaced with the shortest matching prefix from a dictionary.

In the naive approach, we traverse the given sentence, and for each word, we compare it with each prefix in the given dictionary to find the shortest matching prefix against it, if any. To make sure that we get to the right prefix, we store the respective lengths of prefixes with them. Additionally, we keep track of the shortest prefix as well. If, at any point, a match is found, we compare its length with the length of the shortest match found up to that point. If it is shorter than the current shortest prefix, we update the value of the shortest prefix.

In this approach, we iterate through each word in the sentence, which takes O(n)O(n) time, where nn is the number of words in a sentence. For each word, we iterate over the prefixes in the dictionary, which takes O(d)O(d) time, where dd is the number of prefixes in the dictionary. Therefore, the overall time complexity for this approach is O(n×d)O(n \times d).

Optimized approach using trie

Searching for the shortest prefixes for all the words in the given sentence requires repeated searches in the dictionary. While this would be an expensive proposition if we keep our dictionary words in data structures like arrays and linked lists, some more advanced data structures, such as triesA trie is visualized as a tree of characters that allows storing strings as graphs. A trie stores a word in a top-down manner where all words having common leading characters (prefixes) have a common parent., help reduce our search time complexity. In this approach, we first store all the dictionary prefixes in a trie and then find the shortest prefix against each word of the sentence so that we can perform the required replacement.

To store the dictionary prefixes in the trie, we start from its root node and perform the following steps repeatedly until we’ve stored all the words:

  • We check if the current character of the dictionary prefix is listed among the immediate children of the current node.

    • If it doesn’t exist, we create a new trie node for this character as a child of the current node and move to this new trie node.

    • If it exists among the children, we simply move to that node.

  • If the current character is the last character of a given dictionary prefix, we use a flag to mark the trie node holding this last character. This flag represents the completion of a dictionary prefix on the trie. For example, if we have the prefix “dis” in the dictionary, then when we reach “s” and store it in the trie. We mark this node with the flag to represent that the word, “dis”, has been completed.

After we are done creating the trie from the dictionary prefixes, we start to locate the matching prefix for each word of the sentence. Once found, we replace the word in the sentence with it. For example, if the input sentence is “fantastic” and the given dictionary is [[ “fanta”, “tic”, “fan”]], then both “fanta” and “fan” are matching prefixes for “fantastic”, but we replace it with “fan” since it is the shortest of all the found matches. Since we are using a trie, our search automatically picks up the shortest matching prefix, and we don’t need to do it later.

To traverse all the words in the sentence, we store them in a list. Then, for each word, wiw_{i}, perform the following:

  • Start with the first character, wi[0]w_{i}[0], and look at whether the same character exists in any of the children of the root node of the trie.

    • If it exists, it implies that the prefix for wiw_{i} exists, and we can continue as follows:

      • For remaining characters, keep looking for the matching character in the trie one by one.

      • If at any point while searching and matching, we reach a node that is flagged for being the last character, we stop and return this prefix as the shortest matching prefix for wiw_{i}.

    • Otherwise, the prefix against wiw_{i} doesn’t exist, so just move to the next word of the sentence.

Once found, replace the original word wiw_{i} in the list with its matched prefix. Keep doing this until we process the last word in the sentence. In the end, change the list of words back to the string representing the modified sentence and return it as the output.

The slides below illustrate the steps of the solution in detail:

Press + to interact
canvasAnimation-image
1 of 19

Let’s look at the code for this solution below:

main.java
TrieNode.java
Trie.java
class ReplaceWords {
    public String replaceWords(String sentence, List<String> dictionary) {
        Trie trie = new Trie();
        trie.root = new TrieNode();
        for (String prefix: dictionary) {
            trie.insertInTrie(prefix);
        }
        List<String> sentanceList = Arrays.asList(sentence.split(" "));
        List<String> newList = new ArrayList< >();
        for (String str: sentanceList) {
            newList.add(trie.replace(str));
        }
        return String.join(" ", newList);
    }
    // driver code
    public static void main(String[] args) {
        ReplaceWords s = new ReplaceWords();
        String[] sentence = {
            "where there is a will there is a way",
            "the quick brown fox jumps over the lazy dog",
            "oops there is no matching word in this sentence",
            "i was born on twenty ninth february",
            "i dont know where you are but i will find you eventually"
        };
        List<List<String>> dictionary = Arrays.asList(Arrays.asList("wi", "wa", "w"),
                Arrays.asList("qui", "f", "la", "d"),
                Arrays.asList("oops", "there", "is", "no", "matching", "word", "in", "this", "sentence"),
                Arrays.asList("wa", "w", "a", "ty", "nint", "nin", "n", "feb", "februa", "f"),
                Arrays.asList("cool", "how", "sunday", "sun", "x"));
        for (int i = 0; i < sentence.length; i++) {
            System.out.print(i + 1);
            System.out.println(".\tInput sentence: '" + sentence[i] + "'");
            System.out.println("\tDictionary words: '" + dictionary.get(i) + "'");
            System.out.println("\tAfter replacing words: '" + s.replaceWords(sentence[i], dictionary.get(i)) + "'");
            System.out.println(PrintHyphens.repeat("-", 100));
        }
    }
}
Replace Words

Solution summary

Let’s review the optimized approach we have discussed above.

  • Create a trie and store all the dictionary prefixes in it.

  • Traverse the sentence and use the trie to find the shortest matching prefix for each word of the sentence.

  • Once found, replace the original word of the sentence with the matched prefix. We do this for all the words in the sentence.

  • If no matching prefix is found, leave the word as it is and move to the next word in the sentence.

  • Return the modified sentence as the output.

Time complexity

It takes O(m)O(m) time to create a trie from the given dictionary prefixes, where mm is the sum of the number of characters of all the prefixes in the dictionary.

Then, it takes O(n)O(n) time to iterate over each word in the sentence and find its matching prefix in the trie, where nn is the number of words in the sentence.

Therefore, the overall time complexity for this approach is O(n+m)O(n+m).

Space complexity

The space complexity is O(m)O(m), where mm is the sum of the number of characters of all the prefixes in the dictionary.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.