"""
Exercise 1: Count words with a prefix

Implement PrefixCounter with insert(word) and count_prefix(prefix): the
number of inserted words (duplicates count) that start with prefix. Store a
count on each trie node, incremented on every insert passing through it.
"""

class PrefixCounter:
    def insert(self, word):
        # TODO
        pass

    def count_prefix(self, prefix):
        # TODO
        return -1


# --- self-check: do not modify below this line ---
pc = PrefixCounter()
for w in ["apple", "app", "apply", "bat", "app"]:
    pc.insert(w)
got = [pc.count_prefix(p) for p in ["app", "appl", "b", "c", "apple"]]
print(got)
print("PASS" if got == [4, 2, 1, 0, 1] else "FAIL")