# Solution by awice

• #### 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.

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