LeetCode 648: Replace Words

Sort and search

If we sort the dictionary, the first root that is a prefix of a word should be used to replace that word. To make the search efficient, we can binary-search the insert position of word[0] in the sorted dictionary and thereon we do linear-search.

Say $| \texttt{dictionary} | = n$ , the longest root has length $m$ , and there are $k$ words in the sentence. Sorting’s time: $\mathcal{O}(m \cdot n \cdot \lg{n})$ . Time for the prefix searches is $k \cdot m \cdot n$ .

Total time: $\mathcal{O}( m \cdot n \lg{n} + k \cdot m \cdot n ) = \mathcal{O}(m \cdot n \cdot (k + \lg{n}))$ . Space: $\mathcal{O}(m \cdot \lg{n} + |\texttt{sentence}|)$ .

class Solution:
    def find_insert_index(self, w, dictionary) -> int:
        lo, hi = 0, len(dictionary)-1
        while lo <= hi:
            mid = (lo+hi) // 2
            if dictionary[mid] < w:
                lo = mid+1
            else:
                hi = mid-1

        return lo

    def shortest_prefix_of(self, word, dictionary):
        lo = self.find_insert_index(word[0], dictionary)
        if lo == len(dictionary):
            return None

        for i in range(lo, len(dictionary)):
            root = dictionary[i]
            if word.startswith(root):
                return root
            if root[0] != word[0]:
                return None
        return None

    def replaceWords(self, dictionary: List[str], sentence: str) -> str:
        dictionary.sort()

        words = sentence.split(" ")
        replaced_words = []
        for w in words:
            root = self.shortest_prefix_of(w, dictionary)
            replaced_words.append(root or w)

        return " ".join(replaced_words)

Trie

Building the try takes time $m \cdot n$ . Each shortest_prefix_of takes time $m$ .

Total time: $\mathcal{O}(m \cdot (n+k))$ . Space: $\mathcal{O}(m\cdot n + |\texttt{sentence}|)$ .

class TrieNode:
    def __init__(self):
        self.end_of_word = False
        self.edges = {}

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        u = self.root
        for char in word:
            if char not in u.edges:
                u.edges[char] = TrieNode()
            u = u.edges[char]
        u.end_of_word = True
    
    def shortest_prefix_of(self, word):
        u = self.root
        for i, char in enumerate(word):
            if char not in u.edges:
                return None
            u = u.edges[char]
            # Following edge we consumed ith char
            if u.end_of_word:
                return word[:i+1]
        return None

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

unreasonably effective