Compressed Trie (Radix) Insert Count

Problem

Count the nodes of a compressed (radix) trie after inserting all words.

Insert the words into a standard trie, then merge every chain of single-child nodes that is not the end of a word. The remaining non-root nodes are exactly the branch points and word endings.

Return the number of nodes, which also equals the number of edges.

Hint

A compressed trie keeps only nodes that end a word or have at least two children.

Test cases

case 1

in: [["apple","app","apricot"]]

expected: 4

case 2

in: [[]]

expected: 0

case 3

in: [["a"]]

expected: 1

case 4

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

expected: 2

case 5

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

expected: 3

Starter codePython

def radix_trie_nodes(words):
    # Your code here
    pass

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