Count Words with Prefix

Problem

Count how many inserted words start with a given prefix, using a trie.

Insert every word, storing an occurrence count at word endings so duplicates count separately. Walk down the prefix, then sum the occurrence counts in its subtree with a depth-first search.

Return the count, or 0 when the prefix is not present. An empty prefix matches all words.

Hint

Store a count instead of a boolean at word endings so duplicates are counted.

Test cases

case 1

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

expected: 3

case 2

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

expected: 2

case 3

in: [["dog"],"x"]

expected: 0

case 4

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

expected: 1

case 5

in: [[],""]

expected: 0

Starter codePython

def count_words_with_prefix(words, prefix):
    # Your code here
    pass

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