Replace Words

Medium

Asked by:

56 views

Topics:

StringsTrees

In English, we have a concept called root, which can be followed by some other word to form another longer word - let's call this word derivative. For example, when the root "help" is followed by the word "ful", we can form a derivative "helpful".

Given a dictionary consisting of many roots and a sentence consisting of words separated by spaces, replace all the derivatives in the sentence with the root forming it. If a derivative can be replaced by more than one root, replace it with the root that has the shortest length.

Return the sentence after the replacement.

Example 1:

Input: dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"

Example 2:

Input: dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
Output: "a a b c"

Constraints:

1 <= dictionary.length <= 1000
1 <= dictionary[i].length <= 100
dictionary[i] consists of only lower-case letters.
1 <= sentence.length <= 10⁶
sentence consists of only lower-case letters and spaces.
The number of words in sentence is in the range [1, 1000]
The length of each word in sentence is in the range [1, 1000]
Every two consecutive words in sentence will be separated by exactly one space.
sentence does not have leading or trailing spaces.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the `dictionary` and the `sentence`?
Can the `dictionary` or `sentence` be empty or contain null values?
If a word in the `sentence` has multiple prefixes of the same shortest length in the `dictionary`, which prefix should be used?
What characters are allowed in the words in the `dictionary` and in the `sentence`? Can I assume only lowercase English letters, or might there be other characters like uppercase letters, numbers, or punctuation?
If a word in the `sentence` has no prefix in the `dictionary`, should I leave the word as is or return an empty string for that word?

Brute Force Solution

Approach

The brute force method for replacing words involves checking every possible prefix of each word in a sentence against a dictionary of root words. For each word, we try all prefixes to see if they exist in the dictionary. If a shorter prefix matches, we replace the original word with that prefix.

Here's how the algorithm would work step-by-step:

Take the first word of the sentence.
Look at the very beginning of that word (a prefix of length one).
Check if that tiny prefix is a root word in your dictionary.
If it is, replace the original word with this root word.
If it's not, look at a slightly longer prefix (a prefix of length two).
Again, check if this longer prefix is a root word.
Keep doing this, checking longer and longer prefixes until you find one that is a root word or you've reached the end of the word.
If you find a root word, replace the original word in the sentence with that root word.
Move on to the next word in the sentence and repeat the same process: trying prefixes of increasing length until you find a match in your dictionary.
Continue doing this for every word in the sentence.

Code Implementation

def replace_words_brute_force(dictionary, sentence):
    words = sentence.split()
    replaced_words = []

    for word in words:
        shortest_root = None
        for prefix_length in range(1, len(word) + 1):
            prefix = word[:prefix_length]
            # Check if the prefix is a root in the dictionary
            if prefix in dictionary:

                shortest_root = prefix
                break

        # If a root was found, use it; otherwise, keep the original word
        if shortest_root:
            replaced_words.append(shortest_root)
        else:
            replaced_words.append(word)

    # Join the replaced words back into a sentence
    return ' '.join(replaced_words)

Big(O) Analysis

Time Complexity

O(N * M * L) – Let N be the number of words in the sentence, M be the average length of a word in the sentence, and L be the number of root words in the dictionary. For each of the N words in the sentence, we iterate through prefixes of increasing length, up to a maximum length of M. For each prefix, we need to check if it exists in the dictionary of root words. Assuming a linear search through the dictionary (which is implied by the problem explanation), this check takes O(L) time. Therefore, for each word, we perform up to M prefix checks, each taking O(L) time, resulting in O(M * L) time per word. Consequently, the overall time complexity is O(N * M * L).

Space Complexity

O(1) – The provided brute force method primarily operates in-place by iterating through the sentence and its words. It only utilizes a few constant space variables to store prefix lengths and perform comparisons. There are no auxiliary data structures like lists, hash maps, or recursion stacks being created that scale with the size of the input. Thus, the auxiliary space complexity remains constant regardless of the number of words in the sentence or the size of the dictionary.

Optimal Solution

Approach

The fastest way to solve this problem is to use a special kind of data structure to quickly check if a word starts with one of the root words. We build this data structure from the list of root words, and then use it to process the sentence.

Here's how the algorithm would work step-by-step:

First, organize the list of root words into a structure that makes it easy to find words based on their beginning letters.
Next, take the sentence and split it into individual words.
For each word in the sentence, check if it starts with any of the root words stored in our organized structure.
If the word starts with a root word, replace the original word with the shortest root word it starts with.
If the word doesn't start with any root words, leave it as it is.
Finally, combine all the (possibly replaced) words back into a single sentence.

Code Implementation

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_root = False

class WordReplacement:
    def __init__(self):
        self.trie_root = TrieNode()

    def build_trie(self, dictionary):
        for root_word in dictionary:
            current_node = self.trie_root
            for char in root_word:
                if char not in current_node.children:
                    current_node.children[char] = TrieNode()
                current_node = current_node.children[char]
            current_node.is_root = True

    def find_replacement(self, word):
        current_node = self.trie_root
        replacement_word = ""
        for char in word:
            if char in current_node.children:
                replacement_word += char
                current_node = current_node.children[char]
                if current_node.is_root:
                    return replacement_word
            else:
                return word
        return word

    def replaceWords(self, dictionary, sentence):
        # Build the trie using the root words
        self.build_trie(dictionary)

        words = sentence.split()
        replaced_words = []

        for word in words:
            # Find the shortest root word that prefixes the current word
            replacement = self.find_replacement(word)
            replaced_words.append(replacement)

        # Join the words back into a sentence
        return " ".join(replaced_words)

def replace_words(dictionary, sentence):
    word_replacer = WordReplacement()
    return word_replacer.replaceWords(dictionary, sentence)

Big(O) Analysis

Time Complexity

O(N * M) – Building the initial data structure (likely a Trie) from the root words takes O(R * L), where R is the number of root words and L is the average length of a root word. Processing the sentence involves splitting it into N words (N being the number of words in the sentence). For each of the N words, we search in the Trie which, in the worst-case (when no replacements occur and the Trie has to be traversed to the depth equal to the current word length), can take up to O(M) time, where M is the maximum length of a word in the sentence. Because we need to check potentially every word in the sentence against every word in the Trie, that gives us O(N * M) complexity for the sentence processing. The complexity of Trie construction is dominated by the cost of searching, giving an overall complexity of O(N * M).

Space Complexity

O(R) – The primary auxiliary space is consumed by the data structure used to organize the root words, which could be a Trie or a hash set. Let R be the total number of characters across all root words. The space required to store the Trie or hash set will depend on the total number of characters in all the root words, resulting in space proportional to R. The split sentence requires space proportional to the number of words in the input sentence, which we'll denote as S, but this is technically modifying the input in place. Replacing words in the sentence does not require additional space. Therefore, the dominant space complexity is determined by the root word data structure which stores R characters, yielding O(R).

Edge Cases

Case	How to Handle
Empty dictionary	Return the original sentence unchanged since no replacements are possible.
Empty sentence	Return an empty string since there are no words to process.
Null dictionary or sentence	Throw an IllegalArgumentException or return null after checking for null inputs.
Dictionary contains an empty string	The empty string will match any word in the sentence, so return a string where all words are replaced with the empty string.
Sentence contains words with no prefixes in the dictionary	These words should remain unchanged in the resulting sentence.
Dictionary contains prefixes that are also words (e.g., 'a' and 'apple')	The solution should still select the shortest prefix ('a' in this case).
Sentence contains leading/trailing/multiple spaces	Trim the sentence and handle multiple spaces between words correctly to avoid empty words.
Large dictionary and sentence	Consider using a Trie data structure for the dictionary to achieve efficient prefix matching.

Empty dictionary

How to Handle:

Return the original sentence unchanged since no replacements are possible.

Empty sentence

How to Handle:

Return an empty string since there are no words to process.

Null dictionary or sentence

How to Handle:

Throw an IllegalArgumentException or return null after checking for null inputs.

Dictionary contains an empty string

How to Handle:

The empty string will match any word in the sentence, so return a string where all words are replaced with the empty string.

Sentence contains words with no prefixes in the dictionary

How to Handle:

These words should remain unchanged in the resulting sentence.

Dictionary contains prefixes that are also words (e.g., 'a' and 'apple')

How to Handle:

The solution should still select the shortest prefix ('a' in this case).

Sentence contains leading/trailing/multiple spaces

How to Handle:

Trim the sentence and handle multiple spaces between words correctly to avoid empty words.

Large dictionary and sentence

How to Handle:

Consider using a Trie data structure for the dictionary to achieve efficient prefix matching.