Counting Words With a Given Prefix - Solution & Explanation

Problem Overview: You are given an array of strings words and a string pref. The task is to count how many words in the array start with the prefix pref. A word is considered valid if its first characters exactly match the prefix.

Approach 1: Iterative Prefix Check (O(n * m) time, O(1) space)

The most direct solution scans every word in the array and checks whether it starts with pref. For each string, compare the first m characters (where m is the length of the prefix). Many languages provide a built‑in operation such as startsWith() or substring comparison, which performs this check efficiently. Since each of the n words may require up to m character comparisons, the time complexity is O(n * m). The algorithm uses constant extra memory O(1). This approach is simple, readable, and usually preferred for small or moderate input sizes involving arrays of strings.

Approach 2: Trie-based Prefix Matching (O(n * m) build, O(m) query, O(n * m) space)

A Trie (prefix tree) stores characters of all words so shared prefixes occupy the same path. Insert every word character by character into the Trie while maintaining a count of words passing through each node. Once built, traverse the nodes corresponding to pref. The stored counter at the final node directly gives the number of words starting with that prefix. Building the structure takes O(n * m) time and space because each character is inserted once. The prefix lookup itself takes O(m). Trie solutions are common in string matching problems when many prefix queries are expected.

Recommended for interviews: The iterative prefix check is what interviewers typically expect for this problem. It demonstrates clean iteration and efficient use of built‑in string operations. The Trie approach shows deeper knowledge of prefix data structures and becomes valuable if the system must answer many prefix queries repeatedly.