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, creatingrootset
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 worstcase 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.