Solution by awice


  • 0

    Approach #1: Brute Force [Accepted]

    Intuition and Algorithm

    For each word in the sentence, find the shortest prefix that is a root by checking all of them starting with the shortest. Then, replace the word with that prefix, keeping the original word if no prefix was found.

    Python

    class Solution(object):
        def replaceWords(self, roots, sentence):
            rootset = set(roots)
    
            def replace(word):
                for i in xrange(1, len(word)):
                    if word[:i] in rootset:
                        return word[:i]
                return word
    
            return " ".join(map(replace, sentence.split()))
    

    Complexity Analysis

    • Time Complexity: Let $$R$$ be the length of the roots array, $$N$$ be the number of words in the sentence, and $$K$$ be the longest word in the sentence or in roots. Then, creating rootset is $$O(R)$$, and replacing each word is $$O(N * K^2)$$ as for each word ($$O(N)$$), we may check every prefix ($$O(K^2)$$), and we have to build them from scratch. In total, this is $$O(N*K^2 + R)$$ time complexity.

    • Space Complexity: We need $$O(R)$$ space to store the root set, $$O(NK)$$ space to store the answer, and store intermediate prefixes. In total, this is $$O(NK + R)$$ space complexity.


    Approach #2: Tries [Accepted]

    Intuition

    Checking when we have seen a prefix of a word is an ideal operation for Tries (Prefix Trees.) Using a Trie, we can check whether any prefixes of a word are a root in linear time.

    Algorithm

    We create a Trie structure to handle inserting nodes and finding the first prefix.

    When inserting a word like roots[2] = 'cat', we create a path from the root node of the trie down 3 nodes. At the end of the insertion, we will have the nodes root, X = root.children['c'], Y = X.children['a'], and Z = Y.children['t']. Additionally, Z.end = 2, the index where that root was found. We store indices of roots as a compact way to retrieve the found word after.

    When finding the first prefix of a word, we go down the tree in the same manner. If there is no node, then the prefix wasn't found. If node.end is not None, then we have found the root roots[node.end].

    One other optimization we've used is that roots that are prefixes of other roots dominate those other roots, so we don't need to consider them. This doesn't change the worst-case complexity, but it's something to think about. We've marked these lines with the #truncate comment where appropriate.

    Here we have showcased two solutions: one more general, and a more compact variant specific to Python that uses default dictionaries.

    Python

    class TrieNode(object):
        __slots__ = 'children', 'end'
        def __init__(self):
            self.children = {}
            self.end = None
    
    class Trie(object):
        def __init__(self):
            self.root = TrieNode()
    
        def insert_with_truncation(self, word, index):
            cur = self.root
            for char in word:
                if char not in cur.children:
                    cur.children[char] = TrieNode()
                cur = cur.children[char]
                #alternatively:
                #cur = cur.children.setdefault(char, TrieNode())
                if cur.end is not None: return #truncate
            cur.end = index
            cur.children = {} #truncate
    
        def find_prefix(self, word):
            cur = self.root
            ans = ''
            for char in word:
                if char not in cur.children:
                    break
                cur = cur.children[char]
                if cur.end is not None:
                    return cur.end
    
    class Solution(object):
        def replaceWords(self, roots, sentence):
            trie = Trie()
            for i in range(len(roots)):
                trie.insert_with_truncation(roots[i], i)
    
            def replace(word):
                root_index = trie.find_prefix(word)
                if root_index is None:
                    return word
                else:
                    return roots[root_index]
    
            ans = []
            for word in sentence.split():
                ans.append(replace(word))
            return " ".join(ans)
    

    Alternate Implementation

    class Solution(object):
        def replaceWords(self, roots, sentence):
            _trie = lambda: collections.defaultdict(_trie)
            trie = _trie()
            END = True
            for root in roots:
                cur = trie
                for letter in root:
                    cur = cur[letter]
                cur[END] = root
    
            def replace(word):
                cur = trie
                for letter in word:
                    if letter not in cur: break
                    cur = cur[letter]
                    if END in cur:
                        return cur[END]
                return word
    
            return " ".join(map(replace, sentence.split()))
    

    Complexity Analysis

    • Time Complexity: Let $$R$$ be the length of the roots array, $$N$$ be the number of words in the sentence, and $$K$$ be the longest word in the sentence or in roots. Then, creating the trie is $$O(RK)$$, and replacing each word is $$O(NK)$$ as we may check every prefix, and we have to build them from scratch. In total, this is $$O(NK + RK)$$ time complexity.

    • Space Complexity: We need $$O(RK)$$ space to store the trie, and $$O(NK)$$ space to store the answer. In total, this is $$O(NK + RK)$$ space complexity.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.