Counting Words With a Given Prefix

• Create a TrieNode class with children (an array of TrieNodes of size 26) and an integer count to track how many words pass through or end at this node.
• Initialize a root TrieNode.
• For each word in the words array, insert it into the Trie:
  • Start from the root.
  • For each character c in the word:
    • Find the corresponding child node. If it doesn't exist, create it.
    • Move to the child node.
    • Increment the count of the child node.
• To find the number of words with the given prefix pref:
  • Start from the root.
  • Traverse the Trie according to the characters in pref.
  • If at any point a character does not have a corresponding child node, it means no word has this prefix, so return 0.
  • If the traversal is successful, the count of the final node reached is the answer.

First, we define a TrieNode class. Each node will contain an array of children (one for each letter of the alphabet) and a counter, count, to track how many words pass through this node.

We then build the Trie. We iterate through each word in the words array. For each word, we traverse the Trie from the root, creating new nodes as necessary. At each node along the path for the word, we increment its count.

After the Trie is built, we search for the prefix pref. We traverse the Trie according to the characters in pref.

If we can successfully traverse the entire prefix, the count at the final node gives us the number of words that start with pref.

If at any point during the traversal we find that a path for a character does not exist, it means no word has this prefix, so we can immediately return 0.

This approach is highly efficient if you need to perform many prefix searches on the same set of words, as the expensive part (building the Trie) is done only once. However, for a single search as required by this problem, the overhead of building the Trie makes it less efficient than a simple linear scan.

1class TrieNode {2    TrieNode[] children;3    int count;4 5    public TrieNode() {6        children = new TrieNode[26];7        count = 0;8    }9}10 11class Solution {12    public int prefixCount(String[] words, String pref) {13        TrieNode root = new TrieNode();14 15        // Build the Trie16        for (String word : words) {17            TrieNode curr = root;18            for (char c : word.toCharArray()) {19                int index = c - 'a';20                if (curr.children[index] == null) {21                    curr.children[index] = new TrieNode();22                }23                curr = curr.children[index];24                curr.count++;25            }26        }27 28        // Search for the prefix29        TrieNode curr = root;30        for (char c : pref.toCharArray()) {31            int index = c - 'a';32            if (curr.children[index] == null) {33                return 0; // Prefix not found34            }35            curr = curr.children[index];36        }37 38        return curr.count;39    }40}