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}

• Initialize count = 0.
• Get the length of the prefix, prefLen.
• For each word in the words array:
  • First, check if word.length() is less than prefLen. If it is, continue to the next word.
  • If the word is long enough, assume it's a match by setting a flag isPrefix = true.
  • Loop from i = 0 to prefLen - 1:
    • Compare word.charAt(i) with pref.charAt(i).
    • If the characters do not match, set isPrefix = false and break the inner loop.
  • After the inner loop, if isPrefix is still true, increment count.
• Return count.

We initialize a counter variable count to zero. We loop through every word in the words array.

For each word, we first check if its length is less than the prefix's length. If it is, the word cannot possibly have pref as a prefix, so we skip to the next word.

If the word is long enough, we proceed to compare it with the prefix character by character. We can use an inner loop for this. We iterate from the first character up to the length of the prefix. In each iteration, we compare the character from the word with the corresponding character from pref.

If we find any mismatch, we know it's not a prefix, and we can stop checking this word and move to the next one.

If the inner loop completes without finding any mismatches, it means the word starts with the prefix. We then increment our count.

After checking all the words, the final count is our answer.

1class Solution {2    public int prefixCount(String[] words, String pref) {3        int count = 0;4        int prefLen = pref.length();5        for (String word : words) {6            if (word.length() >= prefLen) {7                boolean match = true;8                for (int i = 0; i < prefLen; i++) {9                    if (word.charAt(i) != pref.charAt(i)) {10                        match = false;11                        break;12                    }13                }14                if (match) {15                    count++;16                }17            }18        }19        return count;20    }21}

• Initialize a counter count to 0.
• For each word in the words array:
  • Use the built-in startsWith() method to check if word.startsWith(pref) is true.
  • If it is true, increment count.
• After iterating through all the words, return count.

The algorithm is very simple. We initialize a counter count to 0.

We then iterate through each word in the words array.

For each word, we call word.startsWith(pref). This method returns true if the word begins with the specified pref string, and false otherwise.

If the method returns true, we increment our count.

After the loop has finished checking all the words, the value of count is the total number of words that have pref as a prefix, which we then return.

This approach is not only concise and easy to read but also leverages the optimized implementation of the standard library. For a single query, this is the most efficient solution.

1class Solution {2    public int prefixCount(String[] words, String pref) {3        int count = 0;4        for (String word : words) {5            if (word.startsWith(pref)) {6                count++;7            }8        }9        return count;10    }11}