Radix Trie Edge Split Count

Problem

Insert words one at a time into a compressed (radix) trie whose edges carry string labels. When an insertion diverges in the middle of an existing edge, that edge splits into a prefix edge and a suffix edge; when the word ends in the middle of an edge, the edge splits there too. Return the total number of edge splits across all insertions. Words are non-empty lowercase strings; duplicates are allowed.

Hint

Walk character by character; on a partial edge match, replace the edge with a new middle node and two edges.

Test cases

case 1

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

expected: 1

case 2

in: [["abcde","abcfg","ab"]]

expected: 2

case 3

in: [["abcd","abef","ab"]]

expected: 1

case 4

in: [["a","ab","abc"]]

expected: 0

Starter codePython

def radix_split_count(words):
    # Your code here
    pass

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