Counting Words With a Given Prefix — Trie vs Linear Scan

Problem Statement#

LeetCode 2185 — Counting Words With a Given Prefix | Difficulty: Easy

You are given an array of strings words and a string pref.

Return the number of strings in words that contain pref as a prefix.

A prefix of a string s is any leading contiguous substring of s.

Example:

Input:  words = ["pay","attention","practice","attend"], pref = "at"
Output: 2
Explanation: "attention" and "attend" start with "at".

Constraints:

• 1 <= words.length <= 100
• 1 <= words[i].length, pref.length <= 100
• Lowercase English letters only.

Why This Problem Matters#

Counting Words With a Given Prefix looks deceptively trivial — the LeetCode "easy" tag is correct. Yet it appears in real Amazon and Google phone screens precisely because the follow-up is what matters: "Now answer one million prefix queries." The interviewer wants to see whether you instinctively reach for a trie when the query workload changes, or whether you stay stuck on the obvious linear scan.

The lesson is foundational: the trie is the right tool when the query count exceeds O(N). The same insight drives autocomplete, search-as-you-type suggestions, and any FAANG service that batches prefix lookups against a static dictionary.

The Core Insight#

There are two regimes:

1. One query, one shot — linear scan over words checking startswith(pref) is O(N times L). With N <= 100 and L <= 100, that is at most 10,000 character comparisons. The trie is overkill.
2. Many queries, same word list — build the trie once with a cnt field on each node (count of words passing through). Each query becomes a walk of length P (prefix length), returning cnt at the prefix tip. Build is O(sum of L), query is O(P).

The trie pattern here is the same counted-trie augmentation we saw in Sum of Prefix Scores: increment cnt at every node along the insert path. The query then collects no sum — it returns the single count at the terminal node of the prefix walk.

Visual Dry Run#

Words: ["pay", "attention", "practice", "attend"], query pref = "at".

Trie with cnt at each node:

root
 |-- p (cnt=2)
 |    |-- a (cnt=1) -- y (cnt=1, END "pay")
 |    |-- r (cnt=1) -- a -- c -- t -- i -- c -- e (END "practice")
 |
 |-- a (cnt=2)
      |-- t (cnt=2)
           |-- t (cnt=2)
                |-- e (cnt=2)
                     |-- n (cnt=2)
                          |-- t (cnt=1, END "attend")
                          |-- d (cnt=0?) ...
                     |-- d (cnt=1, END "attend")
                |-- ention path (cnt=1)

Walk "at" → a (cnt=2) → t (cnt=2). Return 2. Both "attention" and "attend" pass through the t node at depth 2.

For the linear scan: iterate ["pay","attention","practice","attend"], check each against "at". Two hits. O(4 times 2) comparisons.

Solution (Optimal) — Two Approaches#

Python — Linear Scan (One Query)#

class Solution:
    def prefixCount(self, words: list[str], pref: str) -> int:
        return sum(1 for w in words if w.startswith(pref))

Python — Trie (Many Queries)#

class TrieNode:
    __slots__ = ("children", "cnt")
    def __init__(self):
        self.children = {}
        self.cnt = 0
 
class Solution:
    def prefixCount(self, words: list[str], pref: str) -> int:
        root = TrieNode()
        for w in words:
            node = root
            for ch in w:
                if ch not in node.children:
                    node.children[ch] = TrieNode()
                node = node.children[ch]
                node.cnt += 1
        node = root
        for ch in pref:
            if ch not in node.children:
                return 0
            node = node.children[ch]
        return node.cnt

JavaScript#

// Linear scan
var prefixCount = function(words, pref) {
  return words.filter(w => w.startsWith(pref)).length;
};
 
// Trie variant for many queries
class TrieNode {
  constructor() {
    this.children = {};
    this.cnt = 0;
  }
}
 
function buildTrie(words) {
  const root = new TrieNode();
  for (const w of words) {
    let node = root;
    for (const ch of w) {
      if (!node.children[ch]) node.children[ch] = new TrieNode();
      node = node.children[ch];
      node.cnt++;
    }
  }
  return root;
}
 
function queryPrefix(root, pref) {
  let node = root;
  for (const ch of pref) {
    if (!node.children[ch]) return 0;
    node = node.children[ch];
  }
  return node.cnt;
}

Complexity#

• Linear scan: O(N times L) per query, O(1) extra space.
• Trie: O(sum of L) build, O(P) per query, O(sum of L) space.

Trie wins when total queries Q > N (amortise the build over many queries).

Common Mistakes#

1. Comparing prefix length naively — if w[:len(pref)] == pref works but creates a substring, marginally slower than startswith.
2. Building the trie inside the function on every call — defeats the entire point. The trie is for amortised multi-query workloads.
3. Returning 0 on partial match — if the trie walk completes the full prefix, return cnt; only return 0 if the walk fails midway.
4. Forgetting to increment cnt at every node, not just terminal — terminal cnt counts exact matches, not prefix matches.
5. Worrying about Unicode for an English-only problem — the children dict handles any alphabet anyway.
6. Using a 26-array for children "for performance" — fine, but for 100-character constraints, dict is just as fast and cleaner.

Interview Tips#

• Open with the linear scan. State its complexity. Acknowledge it solves the problem.
• Ask the interviewer: "Is this a one-shot query, or will we be running many prefix counts?" That single question signals senior judgment.
• If multi-query, pivot to the trie. Walk through the build phase and the query phase.
• State the break-even: "Trie pays off once Q > N."
• Mention that this is the same counted-trie augmentation as autocomplete and search suggestion services.

Follow-up Questions#

• Online updates (insert and count interleaved)? The trie supports incremental inserts; counts stay accurate.
• Count words with pref as a suffix? Build a reverse trie of words; query with reversed(pref).
• Count words containing pref as a substring? Trie alone is not enough — switch to a suffix automaton or generalised suffix tree.
• Top-k longest matches with prefix? DFS subtree at the prefix tip, collect top-k by length.
• Memory pressure with 10^7 words? Compress to a Patricia (radix) trie.

Key Takeaways#

• Counting Words With a Prefix has two regimes: linear scan for one query, trie for many.
• The counted-trie augmentation (cnt at every node) returns the answer in O(P) per query.
• Always ask the interviewer about query volume before picking the data structure.
• Trie build is O(sum of L), trie query is O(P) — break-even is Q > N queries.
• startswith in Python and startsWith in JavaScript are O(P) without substring allocation — use them.
• This is the foundational pattern behind autocomplete, search suggestions, and FAANG prefix services.