Count the distinct prefixes in a word list

Scenario

A dictionary app builds an index so that it can suggest words while you type. The index needs one entry for every different start of a word, such as c, ca and car for the word car.

Before building it, the team wants to know how big it will be. You get the word list, and you must count the different non-empty prefixes.

Your task

Write count_prefixes(words).

words is the word list, in lowercase letters. A word can appear more than once.
A prefix of a word is its first few letters, from 1 letter up to the whole word.
Return how many different prefixes all the words have together. A prefix shared by several words counts once.

Examples

Example 1 (traced)#

text2 lines

Input:  words = ["car", "cat", "cart"]
Output: 5

| Word | Its prefixes |\n|---|---|\n| car | c, ca, car |\n| cat | c, ca, cat |\n| cart | c, ca, car, cart |\n\nThe different ones are c, ca, car, cat and cart: 5.

Example 2#

text2 lines

Input:  words = ["a", "a", "a"]
Output: 1

Every copy has the same single prefix, a, so the count is 1.

Example 3#

text2 lines

Input:  words = ["ab", "cd"]
Output: 4

The words share nothing: a, ab, c and cd.

Constraints

1 ≤ length of words ≤ 5000
Every word has 1 to 20 lowercase letters (a to z)

What does the size limit tell you?

There can be 5,000 words of 20 letters, so up to 100,000 prefixes in all. Writing every prefix into a set of strings costs the letters of each prefix again and again.

A trie makes one node for each different prefix and reads each letter of each word once.

Scenario

A dictionary app builds an index so that it can suggest words while you type. The index needs one entry for every different start of a word, such as c, ca and car for the word car.

Before building it, the team wants to know how big it will be. You get the word list, and you must count the different non-empty prefixes.

Your task

Write count_prefixes(words).

words is the word list, in lowercase letters. A word can appear more than once.
A prefix of a word is its first few letters, from 1 letter up to the whole word.
Return how many different prefixes all the words have together. A prefix shared by several words counts once.

Examples

Example 1 (traced)#

text2 lines

Input:  words = ["car", "cat", "cart"]
Output: 5

| Word | Its prefixes |\n|---|---|\n| car | c, ca, car |\n| cat | c, ca, cat |\n| cart | c, ca, car, cart |\n\nThe different ones are c, ca, car, cat and cart: 5.

Example 2#

text2 lines

Input:  words = ["a", "a", "a"]
Output: 1

Every copy has the same single prefix, a, so the count is 1.

Example 3#

text2 lines

Input:  words = ["ab", "cd"]
Output: 4

The words share nothing: a, ab, c and cd.

Constraints

1 ≤ length of words ≤ 5000
Every word has 1 to 20 lowercase letters (a to z)

What does the size limit tell you?

There can be 5,000 words of 20 letters, so up to 100,000 prefixes in all. Writing every prefix into a set of strings costs the letters of each prefix again and again.

A trie makes one node for each different prefix and reads each letter of each word once.