Solution: Total Number of Words in a Trie

Statement

Given a trie data structure that represents an array of words, words, determine the total number of words stored in it.

Constraints:

• $0\leq$ words.length $\leq 10^3$

• $1\leq$ words[i].length $\leq45$

• All words[i] consist of lowercase English alphabets

Solution

The solution leverages the given trie data structure to efficiently organize and process a array of words. A trie represents each word as a sequence of nodes, with each node corresponding to a letter in the word. This ensures quick access to words based on common prefixes. The algorithm starts at the root node and recursively explores all child nodes while keeping the count of the total words. This effectively enumerates all possible word combinations.

Here are the steps of this solution:

1. Initialize a counter, result, to 0.

2. Traverse the complete trie. Start from the root node and process each node encountered as follows:

   1. If the node marks the end of a word, increment the result counter.

   2. Recursively traverse all non-null children nodes of the current node.

3. Return result.

Let’s look at the illustration below to better understand the solution: