# Autocomplete - Advanced Data Structures / Trie

its possible to solve it during the insert operation into the trie and without keeping frequencies:

``````class TrieNode():
def __init__(self, c="\$"):
self.c = c
self.children = {}

def insert(self, word, i=0):
# mink is the minimum depth at which the word can be autocompleted
mink = math.inf
if word[i] not in self.children:
# if we inserted a new path in the trie
# this could be the minimum depth to reach this word
mink = i
self.children[word[i]] = TrieNode(word[i])
if i == len(word)-1:
# if the paths to this word already existed
# the point of insertion could be the minimum depth
mink = i
else:
# the minimum depth could be somewhere down the trie
mink = min(mink, self.children[word[i]].insert(word, i+1))
return mink

def __repr__(self):
return self.c

def autocomplete(words: List[str]) -> int:
trie = TrieNode()
mink = 0
for word in words:
mink += 1+trie.insert(word)
return mink
``````

“Once the frequency becomes 1 we know that there is only 1 word left in this branch of the trie so we can stop searching”, but in the solution example when adding ‘hill’, every node on that path already had a freq of 2, right? (Looking at the last and second last slide of the explanation). It appears that if every node has freq of 2 on the trie path of a word, the given algorithm just returns the length of the full word, but then in that case couldn’t multiple words have the same shortcut? For example for test case #4, do words ‘aaaaa’ and ‘a’, both have ‘a’ as their shortcut, since they both add 1 to the count or am I mistaken?

I can’t figure out if my solution is correct, all tests are passed, but still have doubts.

class Node:
def init(self):
self.children = {}
self.is_completed = False

def autocomplete(words: List[str]) → int:
root = Node()
result = 0

``````for word in words:
curr = root
steps = 0

for char in word:
steps += 1
if char not in curr.children:
if steps != -1:
result += steps
steps = -1
curr.children[char] = Node()
curr = curr.children[char]
curr.is_completed = True
if steps != -1:
result += steps

return result
``````