How many words start with a given prefix?

Strings and tries Mid-level Python 3.13+ Kotlin 2.4+ Reviewed 1 Nov 2026 By Best Latest Apps

Predict the output

What does this print?

Python 3.13

words = ["car", "card", "care", "cat", "dog"]
three = sum(w.startswith("car") for w in words)
print(three, sum(w.startswith("ca") for w in words))

Options3 41 43 3

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 3 4

Right: car, card and care; then cat as well.

The scan is O(total letters) per question; a trie answers the same question in O(prefix length) after one build.

Why not the others?

B 1 4. startswith counts every word with that start, not just exact matches.
C 3 3. cat also starts with 'ca'.

A trie built from car, card, care, cat and dog, with the path walked for the prefixes ca and car and the number of words found under the last node.

Steps come from running the Python solution.

Text version

prefix 'ca':

Trie (✓ = word ends here):

root
- c
  - a
    - r ✓
      - d ✓
      - e ✓
    - t ✓
- d
  - o
    - g ✓

Walk to root
Walk to c
Walk to a

Result: 4

prefix 'car':

Trie (✓ = word ends here):

root
- c
  - a
    - r ✓
      - d ✓
      - e ✓
    - t ✓
- d
  - o
    - g ✓

Walk to root
Walk to c
Walk to a
Walk to r (word ends here)

Result: 3

30-second answer

A trie stores words letter by letter in a tree; words sharing a start share a path. Store at each node how many words pass through it. Building costs O(total letters); each prefix question walks at most its own length, O(p), and reads the count at the last node. With T total letters that is O(T + p) time and O(T) space.

Practise saying it · 45 s. No recording, just a timer

Explain counting words by prefix with a trie.

Say your answer out loud, then check which of these points you covered:

Path per word
Count at each node
O(p) per question

Deep dive

The 'count at each node' trick is the template for prefix counting and suggestions.

A dict of children handles any alphabet; a 26-slot list is faster for lowercase letters.

For one question only, a linear scan with startswith is simpler; the trie pays off over many questions.

Python solution Ran on Python 3.13.5 · mypy --strict

Python 3.13

class TrieNode:
    def __init__(self) -> None:
        self.next: dict[str, TrieNode] = {}
        self.passes = 0  # words that go through this node


def count_with_prefix(words: list[str], prefix: str) -> int:
    root = TrieNode()
    root.passes = len(words)  # every word starts with ""
    for w in words:
        node = root
        for ch in w:
            node = node.next.setdefault(ch, TrieNode())
            node.passes += 1
    node = root
    for ch in prefix:  # walk the prefix letter by letter
        step = node.next.get(ch)
        if step is None:
            return 0
        node = step
    return node.passes

Kotlin Ran on Kotlin 2.4.21 · JDK 21.0.12.1

Kotlin 2.4

class TrieNode {
    val next = HashMap<Char, TrieNode>()
    var passes = 0 // words that go through this node
}

fun countWithPrefix(words: List<String>, prefix: String): Int {
    val root = TrieNode()
    for (w in words) {
        var node = root
        for (ch in w) {
            node = node.next.getOrPut(ch) { TrieNode() }
            node.passes++
        }
    }
    root.passes = words.size // every word starts with ""
    var node = root
    for (ch in prefix) node = node.next[ch] ?: return 0
    return node.passes
}

Common mistakes

Counting only words that end at the node, not words that pass through it.
Forgetting the empty prefix, which matches every word.

Senior take & follow-ups

Say what each node stores before coding.

Follow-up questions

Think of your answer first, then open the hint.

How do you delete a word?
Show hint
Walk its path, decrement each count, and drop nodes whose count reaches zero.
How much memory does a trie use?
Show hint
Up to one node per letter stored, which can exceed a hash set of the words; shared prefixes reduce it.

What each operation costs: Trie · KMP Algorithm · Rabin Karp · String Matching

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.