autocomple-explaination.md

6. Autocomplete with Tries

Design:

1. TrieNode:
   • Insert operation:
     • Takes O(1), just checking if char is not in children, this operation isn't needed, thanks to the defaultdict
   • Suffixes operation:
     • O(n * m): iterate over children + the suffixes operation with the children of each child
2. Trie:
   • Insert operation:
     • Takes O(n), iterate over each char in word, creating a new TrieNode, assigning as node for next iteration
     • Loop completed, set node.is_word to True
   • Find operation:
     • Takes O(n), iterate over each char in word, get char in node.children, assign children[char] as node for next iteration

Time Complexity:

• insert and find: Both takes O(n), cause 1 iteration per char
• suffixes: O(n * m): iterate over children + the suffixes operation with the children of each child

Space Complexity:

• insert: O(n), the auxiliary space used by the algorithms assigning the node and keep it update while the process is executed
• suffixes: O(n * m), results variable will occupy n + m, plus the n * m of the recursive stack