#648

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Replace Words

Replace words in a sentence using the shortest root from a dictionary, applying efficient array scanning and hash lookup techniques.

array hash table string trie

Problem Statement

Given a dictionary of root words and a sentence, you need to replace every word in the sentence that is a derivative of a root in the dictionary with its corresponding root. If a word can be formed from multiple roots, choose the root with the shortest length. Return the updated sentence after all replacements are made.

For example, for dictionary = ["cat", "bat", "rat"] and sentence = "the cattle was rattled by the battery", you should replace 'cattle' with 'cat', 'rattled' with 'rat', and 'battery' with 'bat', resulting in the sentence "the cat was rat by the bat".

Examples

Example 1

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

Output: "the cat was rat by the bat"

Example details omitted.

Example 2

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

Output: "a a b c"

Example details omitted.

Constraints

1 <= dictionary.length <= 1000
1 <= dictionary[i].length <= 100
dictionary[i] consists of only lower-case letters.
1 <= sentence.length <= 106
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.

Solution Approach

Array Scanning

The solution starts by scanning through each word in the sentence. For each word, check if it starts with any root from the dictionary. This can be efficiently done by iterating through the dictionary and finding the shortest match for each word.

Hash Table Lookup

Using a hash table or trie, you can store the roots for quick lookup. This helps in identifying the shortest root for each derivative word in the sentence. The hash table stores the roots as keys, enabling constant-time lookup for each word.

Efficient Replacement

Once the shortest root is found for a word, replace it in the sentence. Construct the final sentence by replacing all the words that have a matching root, ensuring the output sentence is correctly formatted with spaces.

Complexity Analysis

Metric	Value
Time	O(d \cdot w + s \cdot w)
Space	O(d \cdot w + s \cdot w)

The time complexity is O(d * w + s * w), where d is the number of roots, w is the maximum length of a root, and s is the number of words in the sentence. The space complexity is also O(d * w + s * w), as we need to store the dictionary roots and process each word in the sentence for matching roots.

What Interviewers Usually Probe

Tests understanding of efficient string matching and optimization techniques.
Tests familiarity with hash tables and efficient lookup methods.
Evaluates the ability to handle large input sizes and optimize for time and space complexity.

Common Pitfalls or Variants

Common pitfalls

Overlooking edge cases such as words that have no matching root.
Incorrectly handling cases where multiple roots can match, not picking the shortest.
Not optimizing the search for roots, leading to slower solutions.

Follow-up variants

Use a trie instead of a hash table to optimize root lookup.
Limit the dictionary size or impose stricter constraints on the sentence.
Allow multiple words to be replaced by multiple roots (e.g., handle word sequences).

FAQ

What is the main pattern for solving the Replace Words problem?

The main pattern involves array scanning combined with efficient hash table lookup to replace words in the sentence with their shortest root.

How can I optimize the replacement process for large sentences?

By using a hash table or trie to store the roots and performing a lookup for each word in the sentence, you can achieve efficient replacements even with large inputs.

What is the time complexity of the Replace Words problem?

The time complexity is O(d * w + s * w), where d is the number of dictionary words, w is the maximum length of a word, and s is the number of words in the sentence.

What if there are no matching roots for a word in the sentence?

If a word has no matching root, it remains unchanged in the sentence. Only words that can be replaced by a root are modified.

How can I handle multiple roots that match a word in the sentence?

You should always replace the word with the shortest root that matches it. This ensures that the solution meets the problem's requirements.

terminal

Solution

Solution 1: Trie

We can use a trie to store all the roots in the dictionary. Define the trie node class $\text{Trie}$, which contains an array $\text{children}$ of length $26$ to store child nodes, and a boolean variable $\text{is\_end}$ to mark whether it is a complete root.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

class Trie:
    def __init__(self):
        self.children = [None] * 26
        self.is_end = False

    def insert(self, w: str) -> None:
        node = self
        for c in w:
            idx = ord(c) - ord("a")
            if node.children[idx] is None:
                node.children[idx] = Trie()
            node = node.children[idx]
        node.is_end = True

    def search(self, w: str) -> str:
        node = self
        for i, c in enumerate(w, 1):
            idx = ord(c) - ord("a")
            if node.children[idx] is None:
                return w
            node = node.children[idx]
            if node.is_end:
                return w[:i]
        return w


class Solution:
    def replaceWords(self, dictionary: List[str], sentence: str) -> str:
        trie = Trie()
        for w in dictionary:
            trie.insert(w)
        return " ".join(trie.search(w) for w in sentence.split())

Continue Practicing

#692 top k frequent words #720 longest word in dictionary #745 prefix and suffix search