Autocomplete - Advanced Data Structures / Trie

Problems
1

https://algo.monster/problems/autocomplete

2

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
6

“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?

7

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
9

The solution is wrong in that we need to first insert all the words, then call query() for each of the words.

Currently it’s calling query after inserting each word.