Problem of The Day: Replace Words

Problem Statement

Intuition

My initial thought was to use a Trie (prefix tree) for efficient prefix searching. By storing all dictionary words as prefixes in the Trie, I can quickly find the shortest root for each word in the sentence.

Approach

1. Building the Trie: I start by creating an empty Trie. For each root in the dictionary, I insert it into the Trie. Each character of the root is added to the Trie nodes, and I mark the end of a root with a special character (e.g., '#').

2. Processing the Sentence: I split the sentence into individual words. For each word, I traverse the Trie to find the shortest prefix that exists in the Trie. If I find such a prefix, I replace the word with this prefix. If no prefix is found, I keep the word as is.

3. Building the Result: After processing all words, I join them back into a single string to form the final modified sentence.

Complexity

• Time complexity:

  • Building the Trie takes O(K) time, where K is the sum of the lengths of all dictionary words.
  • Searching for each word’s prefix in the Trie takes O(L) time per word, where L is the average length of the words in the sentence.
  • Thus, the overall time complexity is \(O(K + N \cdot L)\), where N is the number of words in the sentence.

• Space complexity:

  • The space complexity for the Trie is O(K), where K is the total number of characters in the dictionary.
  • Storing the result list takes O(N) space.
  • Thus, the overall space complexity is O(K + N).

Code

class Solution:
    def replaceWords(self, dictionary: List[str], sentence: str) -> str:
        words = sentence.split()
        res = []
        trie = {}
        for root in dictionary:
            curr = trie
            for c in root:
                if c not in curr:
                    curr[c] = {}
                curr = curr[c]
            curr['#'] = True

        for word in words:
            curr = trie
            found = False
            for i, c in enumerate(word):
                if '#' in curr:
                    res.append(word[:i])
                    found = True
                    break
                if c not in curr:
                    break
                curr = curr[c]

            if not found:
                res.append(word)

        return ' '.join(res)

Editorial

Approach 1: Hash Set

class Solution:
    def replaceWords(self, dictionary: List[str], sentence: str) -> str:
        word_array = sentence.split()
        dict_set = set(dictionary)

        def shortest_root(word, dict_set):
            # Find the shortest root of the word in the dictionary
            for i in range(len(word)):
                root = word[0:i]
                if root in dict_set:
                    return root
            # There is not a corresponding root in the dictionary
            return word

        # Replace each word in sentence with the corresponding shortest root
        for word in range(len(word_array)):
            word_array[word] = shortest_root(word_array[word], dict_set)

        return " ".join(word_array)

Let d be the number of words in the dictionary, s be the number of words in the sentence, and w be the average length of each word.

• time: O(d * w + s * w^2)
• space: O(d * w + s * w)

Approach 2: Prefix Trie

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


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        current = self.root
        for c in word:
            if current.children[ord(c) - ord("a")] is None:
                current.children[ord(c) - ord("a")] = TrieNode()
            current = current.children[ord(c) - ord("a")]
        current.isEnd = True

    # Find the shortest root of the word in the trie
    def shortest_root(self, word):
        current = self.root
        for i in range(len(word)):
            c = word[i]
            if current.children[ord(c) - ord("a")] is None:
                # There is not a corresponding root in the trie
                return word
            current = current.children[ord(c) - ord("a")]
            if current.isEnd:
                return word[: i + 1]
        # There is not a corresponding root in the trie
        return word


class Solution:
    def replaceWords(self, dictionary: List[str], sentence: str) -> str:
        word_array = sentence.split()

        dict_trie = Trie()
        for word in dictionary:
            dict_trie.insert(word)

        # Replace each word in the sentence with the corresponding shortest root
        for word in range(len(word_array)):
            word_array[word] = dict_trie.shortest_root(word_array[word])

        return " ".join(word_array)

• time: O(dw + sw)
• space: O(dw + sw)