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