Wildcard search with dots

Why this matters

Many search tools accept a pattern with a blank in it. In a crossword you know the word is c?t and the middle letter is missing. In a file search you type report.txt and the dot means "any character". The blank is a wildcard: a symbol that stands for any one of several possible letters.

This lesson adds a wildcard to the trie from the first lesson of this module. The wildcard is the dot character .. A dot in a search pattern matches any single letter. The pattern .ad matches bad, dad and mad, but not pad, because p is not a dot.

The first lesson used a trie to answer exact questions: is this word stored, and does any word start with these letters. Each exact question has one path through the trie. A dot breaks that rule. At a dot, the search does not know which child to follow, so it must try them all. Trying several paths, and returning to an earlier choice when one path fails, is the core skill in this lesson. It is also the basic move in many backtracking problems that appear later in the course.

Start with an exact search

Before dots, recall how an exact search works. Suppose the trie stores bad, dad and mad. To check bad, start at the root. Follow the child labelled b, then a, then d. If you reach the end of the pattern and the node you stand on has its end flag set, the word is stored.

Each step has only one possible next node. The b child either exists or it does not. If it does not, the search stops and the answer is no. This is why an exact search takes time that depends on the length of the word, not on the number of stored words.

A dot changes that. Here is the same walk with the pattern .ad:

1. At the root, the first letter is a dot. The root has three children, b, d and m. We do not know which one the pattern means.
2. Try the b child. From b, the next letter is a, and b has an a child. From that node, the next letter is d, and that child exists and has its end flag set. The pattern matched, so the answer is yes.

In this example the first branch already succeeded, so the search could stop. If the first branch had failed, it would have moved on to the d child and then the m child.

The idea: one step can become several steps

Think of each dot as a fork in a road. A letter is a single road sign. A dot is a sign that says "any of the roads leaving this junction is fine". To find out whether any road leads to a stored word, you walk each road in turn. You stop as soon as one road reaches a stored word.

The same idea works for a whole pattern. Let the walk go down one letter at a time. When it meets a letter, it takes that child only. When it meets a dot, it takes each child in turn and asks the same question for the rest of the pattern. If any answer is yes, the search returns yes. If every answer is no, the search returns no.

This is a recursive search. Recursion means a function that calls itself on a smaller piece of the problem. The smaller piece here is the rest of the pattern, starting from the next node in the trie.

The function needs two pieces of state:

• the node we are standing on in the trie
• the position in the pattern, counted from 0, of the next character to match

When the position equals the length of the pattern, every character has matched. At that point the only thing left to check is whether the current node is a word end. A node that is not a word end is only a stepping stone, so the pattern is not a stored word.

The first worked example: the dictionary bad, dad, mad

Here is the full class. It stores words in a trie and answers pattern searches. Each child is a std::unique_ptr<Node>, a smart pointer that owns the node and frees it automatically when the trie is destroyed. The trie has 26 child slots, one for each lowercase letter.

#include <array>
#include <cstddef>
#include <iostream>
#include <memory>
#include <stdexcept>
#include <string>
#include <string_view>
 
struct Node {
    std::array<std::unique_ptr<Node>, 26> children{};
    bool isEnd = false;
};
 
class WordDictionary {
public:
    void addWord(std::string_view word) {
        Node* current = &root_;
        for (char ch : word) {
            const std::size_t index = letterIndex(ch);
            if (!current->children[index]) {
                current->children[index] = std::make_unique<Node>();
            }
            current = current->children[index].get();
        }
        current->isEnd = true;
    }
 
    bool search(std::string_view pattern) const {
        return searchFrom(&root_, pattern, 0);
    }
 
private:
    Node root_;
 
    static std::size_t letterIndex(char ch) {
        if (ch < 'a' || ch > 'z') {
            throw std::invalid_argument(std::string("not a lowercase letter: ") + ch);
        }
        return static_cast<std::size_t>(ch - 'a');
    }
 
    static bool searchFrom(const Node* node, std::string_view pattern, std::size_t pos) {
        if (pos == pattern.size()) {
            return node->isEnd;
        }
        const char ch = pattern[pos];
        if (ch == '.') {
            for (const auto& child : node->children) {
                if (child && searchFrom(child.get(), pattern, pos + 1)) {
                    return true;
                }
            }
            return false;
        }
        const Node* next = node->children[letterIndex(ch)].get();
        return next != nullptr && searchFrom(next, pattern, pos + 1);
    }
};
 
int main() {
    std::cout << std::boolalpha;
 
    WordDictionary words;
    for (std::string_view w : {"bad", "dad", "mad"}) {
        words.addWord(w);
    }
    std::cout << "search(\"pad\") = " << words.search("pad") << '\n';
    std::cout << "search(\".ad\") = " << words.search(".ad") << '\n';
    std::cout << "search(\"b..\") = " << words.search("b..") << '\n';
    std::cout << "search(\"b.\")  = " << words.search("b.") << '\n';
    std::cout << "search(\"...\") = " << words.search("...") << '\n';
 
    WordDictionary backtrack;
    backtrack.addWord("aaz");
    backtrack.addWord("abc");
    std::cout << "backtrack: search(\"a.c\") = " << backtrack.search("a.c") << '\n';
    std::cout << "backtrack: search(\"a.z\") = " << backtrack.search("a.z") << '\n';
 
    WordDictionary nested;
    nested.addWord("a");
    nested.addWord("ab");
    nested.addWord("abc");
    std::cout << "nested: search(\".\") = " << nested.search(".") << '\n';
    std::cout << "nested: search(\"..\") = " << nested.search("..") << '\n';
    std::cout << "nested: search(\"...\") = " << nested.search("...") << '\n';
    std::cout << "nested: search(\"....\") = " << nested.search("....") << '\n';
 
    try {
        words.addWord("b.d");
    } catch (const std::invalid_argument& e) {
        std::cout << "addWord error: " << e.what() << '\n';
    }
    return 0;
}

Read searchFrom line by line. The first if is the base case: the check that ends the recursion without calling itself. When pos equals the pattern length, the function returns the end flag of the current node. The second if handles the dot. It loops over all 26 child slots, skips the empty ones, and calls itself for each real child with the next position. The loop returns true as soon as one call succeeds. The last part handles a plain letter: take the one child that matches, or report no if it is missing.

Save the program as wildcard_lesson.cpp. Compile and run it with the warning flag on:

g++ -std=c++20 -Wall -o wildcard_lesson wildcard_lesson.cpp && ./wildcard_lesson

Output:

search("pad") = false
search(".ad") = true
search("b..") = true
search("b.")  = false
search("...") = true
backtrack: search("a.c") = true
backtrack: search("a.z") = true
nested: search(".") = true
nested: search("..") = true
nested: search("...") = true
nested: search("....") = false
addWord error: not a lowercase letter: .

The first five lines come from the dictionary bad, dad, mad. The next two lines use the backtracking words, and the next four use the words with prefixes. The last line shows the error from adding a dot. Walk through the lines of the first group.

• search("pad") is false because the root has no child p. The search stops at the first letter.
• search(".ad") is true because the first dot can take the b child, then a, then d.
• search("b.") is false because a pattern of length two can only match stored words of length two. Every stored word has length three, so the walk reaches b, then a, and then the pattern is used up. The node for ba is not a word end, so the answer is no.

The second worked example: backtracking

The first example succeeded on its first branch. The second example needs the search to fail on one branch and try the next. This is called backtracking: go back to an earlier choice and try a different option after a failure.

Store two words, aaz and abc. Search for a.c.

1. The first letter a is a plain letter. The root has an a child. Move there.
2. The second character is a dot. The node for a has two children, a and b. Take the a child first. This leads to the node for aa.
3. The third character is c. The node for aa has only the child z, which came from the stored word aaz. There is no c child, so this branch returns no.
4. Back at the dot, the loop moves on to the b child. This leads to the node for ab.
5. The third character is c. The node for ab has the child c. Move there. The pattern is used up, and the node for abc has its end flag set. The answer is yes.

The loop inside the dot branch is what makes step 4 happen. A search that only tried the first child would stop at step 3 and answer no, which is wrong. The mistakes section below shows that bug with real output.

Here is a third example, with words that are prefixes of each other. Store a, ab and abc. The node for a has its end flag set, and it is also on the way to ab. That is the same situation as car and card in the first lesson. The output for these four searches is the four nested lines above.

. is true because the single letter a is stored. .. is true because ab is stored. ... is true because abc is stored. .... is false because no stored word has four letters. The search reaches a node at depth four only if a stored word has four letters, and none does. This case shows why the end flag check at the bottom of the recursion matters: a path can exist in the trie without a word ending at its last node.

How much work a search does

A search with no dots takes one step per letter, the same as the exact search in the first lesson. Each dot can multiply the work. At a dot the search may visit every child, and each of those children may have its own dots to try.

In the worst case the pattern is all dots, such as ..... Then the search visits every node in the trie up to the pattern's depth. If the trie holds many words that share no beginning, that can be a large part of the trie. Each stored word can add several new nodes, so a large dictionary has many nodes, and an all-dots search may touch a large share of them.

Dots placed after a plain letter are cheaper. A pattern such as ca. visits only the children of the node for ca, which is at most 26 nodes. The more letters the pattern has in front, the fewer nodes the dots can reach.

This is often faster than checking every word one by one. The cost depends on how many nodes the pattern reaches, not on how many words the trie holds in total. This lesson does not try to prove a tight bound. The practical point is that the trie gives you the search tree for free, and the pattern decides how much of it you visit.

Common mistakes

Mistake 1: stopping at the first child

This version of the dot branch returns as soon as it finds one non-empty child, instead of trying each child.

bool searchFirstChildOnly(const Node* node, std::string_view pattern, std::size_t pos) {
    if (pos == pattern.size()) {
        return node->isEnd;
    }
    if (pattern[pos] == '.') {
        for (const auto& child : node->children) {
            if (child) {
                return searchFirstChildOnly(child.get(), pattern, pos + 1);
            }
        }
        return false;
    }
    const Node* next = node->children[pattern[pos] - 'a'].get();
    return next != nullptr && searchFirstChildOnly(next, pattern, pos + 1);
}

Run it on the dictionary ab, cd with the pattern .d. The correct answer is true, because cd matches. The first non-empty child is a, which has no d child, so the buggy version answers false.

first child only, .d = false

The fix is to keep looping. In the working version, searchFrom returns true only when a child succeeds, and otherwise moves on to the next child.

Mistake 2: treating the dot as a letter

If the dot is not checked before the letter is turned into an index, the code computes a number far outside the range 0 to 25:

const Node* next = node->children[pattern[pos] - 'a'].get();

For the dot character, '.' - 'a' is 46 - 97, which is -51. Using that as an array index reads memory that does not belong to the array.

The C++ standard library checks this in this build, and stops the program with an assertion. Here is the real output from a test program that runs this line with the pattern a.c and reaches the dot:

/usr/include/c++/15/array:219: constexpr const std::array<_Tp, _Nm>::value_type& std::array<_Tp, _Nm>::operator[](size_type) const [with _Tp = std::unique_ptr<Node>; long unsigned int _Nm = 26; const_reference = const std::unique_ptr<Node>&; size_type = long unsigned int]: Assertion '__n < this->size()' failed.

The program exits with code 134. Other builds may not check the index, so the program may read garbage and keep running. This is why the working version checks for a dot before it computes an index.

Mistake 3: adding a word that contains a dot

A dot is a wildcard only in a search pattern. A stored word must be real letters. The letterIndex helper throws an error for any character that is not a lowercase letter, so this input is caught when the word is added:

addWord error: not a lowercase letter: .

If you remove that check, a dot would be stored as a letter in the trie, and a later search for a dot would not match it the way you expect.

Mistake 4: copying a unique_ptr

Each child is a std::unique_ptr, which can have only one owner. Copying one is not allowed. A line such as auto copy = root.children[0]; fails to compile. This is the real error from g++ 15.2.0 with -std=c++20 -Wall, cut to the first lines:

errors_wc.cpp: In function ‘int main()’:
errors_wc.cpp:12:32: error: use of deleted function ‘std::unique_ptr<_Tp, _Dp>::unique_ptr(const std::unique_ptr<_Tp, _Dp>&) [with _Tp = Node; _Dp = std::default_delete<Node>]’
   12 |     auto copy = root.children[0];
      |                                ^

To use a child without taking ownership, use .get() to get a plain pointer, as searchFrom does. A plain pointer does not free the node, and the trie keeps ownership.

Mistake 5: forgetting the end flag

A search that returns true whenever the pattern runs out, without checking isEnd, would report prefixes as words. With the dictionary bad, the pattern b. reaches the node for ba and returns true. That is wrong, because ba is not a stored word. The check return node->isEnd; at the bottom of searchFrom is what prevents this.

Practice

Exercise 1

Store the words cat, cut and cot. For each pattern, answer true or false and give a reason in one sentence: c.t, c..., ..., c..t.

Show the answer

c.t is true, because cat, cut and cot all match. c... is false, because the pattern has four letters and no stored word has four letters. ... is true, because the search takes the three dot branches and reaches the end flag of cat. c..t is false, because the pattern has four letters and no stored word has four letters.

Exercise 2

Store the single word ab. Predict the answer for each pattern: a, a., ., ....

Show the answer

a is false, because the node for a exists but has no end flag. a. is true, because ab matches. . is false, because the pattern has one character and the only stored word has two. ... is false for the same reason.

Exercise 3

Using the buggy searchFirstChildOnly function from Mistake 1, store the words ab and cd and predict the result for the pattern .b. Then explain in two sentences why the buggy version gives that answer.

Show the answer

The buggy version returns true for .b, because the first child of the root is a, and ab matches. The explanation is that the function only checks the first non-empty child, so for .b it happens to pick the branch that works. Searching .d picks the same first child a, which has no d, so it returns false even though cd matches.

Exercise 4

Explain why searchFrom returns false when the dot loop finishes without a success. What would go wrong if it returned true instead?

Show the answer

Returning false means no child led to a match, so the answer for this pattern is no. Returning true would make every dot match, even when no child exists. A search such as .. on an empty dictionary would then report true, which is wrong.

Exercise 5

Write the call sequence for searchFrom for the pattern b. on the dictionary bad, where each line shows the node name and the position. Stop when the function returns.

Show the answer

Call 1: node root, position 0, letter b, move to node b. Call 2: node b, position 1, dot, try child a. Call 3: node ba, position 2, which equals the pattern length of 2. The check returns isEnd for node ba, which is false. Back in the dot loop of call 2, there are no other children of b, so the loop ends and the function returns false. Back in call 1, the answer is false.

Summary

• A dot in a pattern matches any single letter, so the search must follow every child at that point.
• The search is recursive: it takes the current node and the position in the pattern, and calls itself on the next character.
• Each dot loops over the children and returns true as soon as one branch succeeds. A failed branch falls through to the next one, which is backtracking.
• The end flag check at the bottom of the recursion makes prefixes of longer words count as non-words.
• Dots near the start of a pattern reach more of the trie than dots near the end, so the cost depends on the pattern.
• Check that a dot never reaches the code that turns a letter into an index, and keep the unique pointers owned by the trie.