Introduction

Looking up words with missing letters is a pattern-matching problem, not just a plain dictionary lookup. The best data structure depends on what “missing letters” means: unknown letters at fixed positions, arbitrary wildcards, or omitted letters where positions may shift.

Start With the Query Model

There are two common interpretations.

The first is fixed-position wildcards, such as c?t or a__le, where the word length and character positions are known.

The second is deletion matching, where some letters are missing and the remaining letters keep order, such as finding words that contain aple as a subsequence.

Those are different problems and call for different indexing strategies.

For Fixed-Position Wildcards, Use a Trie

A trie is a strong default when the pattern length is known and wildcards can occur at particular positions.

The search logic is:

• walk the trie normally for concrete letters
• branch to all children when the query character is a wildcard
• accept only words that end at the same depth as the pattern length

Here is a runnable Python example.

1class TrieNode:
2    def __init__(self):
3        self.children = {}
4        self.is_word = False
5
6class Trie:
7    def __init__(self):
8        self.root = TrieNode()
9
10    def insert(self, word):
11        node = self.root
12        for ch in word:
13            node = node.children.setdefault(ch, TrieNode())
14        node.is_word = True
15
16    def search_pattern(self, pattern):
17        results = []
18
19        def dfs(node, i, path):
20            if i == len(pattern):
21                if node.is_word:
22                    results.append(path)
23                return
24
25            ch = pattern[i]
26            if ch == '?':
27                for next_ch, next_node in node.children.items():
28                    dfs(next_node, i + 1, path + next_ch)
29            elif ch in node.children:
30                dfs(node.children[ch], i + 1, path + ch)
31
32        dfs(self.root, 0, "")
33        return results
34
35trie = Trie()
36for word in ["cat", "cap", "can", "bat", "map"]:
37    trie.insert(word)
38
39print(trie.search_pattern("ca?"))

This works well when the alphabet is moderate and the wildcard count is not too large.

For Many Repeated Fixed-Length Queries, Precompute Masks

If you repeatedly query the same dictionary with patterns of the same length, an indexed hash map can be faster than backtracking through a trie.

For example, the word care can generate masked keys such as:

• '?are'
• 'c?re'
• 'ca?e'
• 'car?'

Store each masked key in a dictionary that maps to matching words. Then lookup is just a hash-table access for one-missing-letter queries.

This approach is fast, but memory grows quickly if you support many wildcard positions per word.

For Omitted Letters With Preserved Order, Tries Are Not Enough

If the query means letters are missing but positions are not fixed, you are closer to subsequence matching.

For example, searching with aple might need to match apple because the remaining letters appear in order. That is a different search problem.

A simple baseline solution is to test each word with a two-pointer subsequence check.

1def is_subsequence(pattern, word):
2    i = 0
3    for ch in word:
4        if i < len(pattern) and pattern[i] == ch:
5            i += 1
6    return i == len(pattern)
7
8words = ["apple", "maple", "ape", "apply"]
9print([w for w in words if is_subsequence("aple", w)])

For very large dictionaries, you would build specialized indexes by length, character positions, or n-grams rather than a plain trie.

Choosing the Right Structure

A practical rule is:

• wildcard at known positions: trie or masked-pattern index
• exactly one or two missing letters at fixed positions: precomputed hash maps are excellent
• missing letters with shifting positions: subsequence-oriented search or more advanced indexing is better
• crossword-like lookup with constraints and many candidate words: group by length first, then filter

Often the best first optimization is not a fancy data structure. It is partitioning the dictionary by word length so impossible candidates are eliminated immediately.

Common Pitfalls

The biggest mistake is using one data structure for every interpretation of "missing letters." Fixed-position wildcards and subsequence matching are not the same task.

Another mistake is ignoring word length. If the pattern length is fixed, length filtering is almost free and removes large parts of the search space.

A third issue is over-indexing. Precomputing every masked variant can explode memory if the dictionary is large and the number of missing positions is unrestricted.

Finally, if wildcard frequency is high, trie branching can become expensive. In that case, length-indexed candidate filtering may beat deep wildcard recursion.

Summary

• The right algorithm depends on what "missing letters" means in the query model.
• For fixed-position wildcards, a trie is a strong and flexible choice.
• For repeated one-letter-missing queries, precomputed masked-pattern maps can be very fast.
• For omitted letters with shifting positions, think subsequence matching instead of tries.
• Grouping words by length is an easy and effective first optimization.
• Define the exact matching rule before choosing the data structure.