Trie Node Count on Insert

Problem

Insert each word into a prefix trie, creating a new node only when the next character is not already present. Return the total number of trie nodes after all insertions, counting the root. Words are non-empty and contain lowercase letters.

Hint

Each shared prefix is stored once, so total nodes equal the number of distinct prefixes plus the root.

Test cases

case 1

in: [["cat","car","dog"]]

expected: 8

case 2

in: [["a","a","a"]]

expected: 2

case 3

in: [["ab","ac","ad"]]

expected: 5

case 4

in: [[]]

expected: 1

Starter codePython

def trie_node_count(words):
    # Your code here
    pass

4 test cases · run your code against them in the editor