Wildcard search with dots in Python

Why this matters

Many search tools accept a pattern instead of an exact word. A word game might give you five boxes where the first letter is "s", the last letter is "e", and the middle letters are unknown. A file search might take report* to mean any file that starts with "report". In both cases one symbol stands for any letter. This symbol is called a wildcard.

This lesson uses the dot as the wildcard. The dot . matches any single letter, so the pattern b.d matches "bad", "bid", "bud" and any other three-letter word that starts with "b" and ends with "d", as long as the word is in the dictionary. The same problem appears in coding interviews under the name "add and search word".

Lesson 02 in this module showed exact search and prefix search in a trie. This lesson changes one rule of that search. A letter in the pattern still has one path to follow. A dot has many paths to follow, so the search must try them all.

Terms used in this lesson

A trie is a tree of letters. The root is an empty starting point. Each step down the tree adds one letter. A path from the root to a node spells a prefix, and a path that ends at a marked node spells a whole word.

A node is one box in the tree. Each node holds its children, which are the nodes one letter further down.

A child of a node is the node reached by one more letter. A node for "b" can have a child for "a", which means "ba" is a prefix in the dictionary.

An end flag is a True or False value on a node. It is True when the path to that node spells a whole word. A node can have children and still be the end of a word. For example, "bad" and "badge" share a path, and the node for "d" in "bad" has its end flag set.

A pattern is the text you search for. In this lesson a pattern is a string made of letters and dots.

A recursive function is a function that calls itself on a smaller problem. The search in this lesson calls itself once per letter of the pattern.

A small worked example

Start with a dictionary of three words: "bad", "dad" and "mad". The trie looks like this. The letter "b" is one child of the root, and so on.

root
 +-- b
 |    +-- a
 |         +-- d (end)
 +-- d
 |    +-- a
 |         +-- d (end)
 +-- m
      +-- a
           +-- d (end)

Now search for the pattern .ad. The first character is a dot, so the search cannot pick one child. It must try the children of the root in turn: "b", then "d", then "m".

1. At the root, the dot matches the child "b". Move down to "b" and look at the next pattern character.
2. The next pattern character is "a". The node "b" has a child "a", so move down to it.
3. The next pattern character is "d". The node "ba" has a child "d", so move down to it.
4. The pattern has no characters left. The node "bad" has its end flag set, so the search returns True.

The search stops at the first success. It did not need to try "d" or "m" at the root.

Now search for .ad in a dictionary that has only "cat" and "dog". At the root the dot tries "c" and then "d". Under "c", the letter "a" leads to "ca", but "ca" has only the child "t", so there is no "d" to match. Under "d", the letter "o" is the only child, so there is no "a" to match. Both branches fail, so the answer is False.

Adding the dot to the search

The exact search from lesson 02 follows one child per letter. The code looks up node.children[ord(ch) - ord("a")], moves to that child, and continues. If the child is missing, the answer is False.

For a dot, the code needs a different rule. It looks at all 26 possible children of the current node. For each child that exists, it tries the rest of the pattern from that child. If any branch returns True, the whole search returns True. If every branch returns False, the search returns False.

In Python the any function does this loop for you. any takes an iterable of values and returns True as soon as one of them is true. It stops at the first True, so it behaves like the early return true in a loop. The expression inside any is a generator expression, which produces one value at a time and does not build a list first.

The search uses a helper method with an index i. The index says which pattern character is being matched now. When i reaches the end of the pattern, the search has matched every character, and the only question left is whether the node is the end of a word.

Here is the full dictionary class. It has add_word to insert a word and search to check a pattern. The insert method is the same as the one in lesson 02. The program also has find_all, which returns every matching word. It is explained below.

The program prints:

pad -> False
bad -> True
.ad -> True
b.. -> True
b... -> False
.. -> False
... -> True
m.d -> True
x.. -> False
 
ba. matches ['bad', 'bar', 'bat', 'bay']
.a. matches ['bad', 'bar', 'bat', 'bay', 'cab']
c.. matches ['cab']
ba matches []

Read the first block. "pad" is False, because no word starts with "p". "bad" is True. "b.." is True, because "bad" has three letters and starts with "b". "b..." is False, because no word in this dictionary has four letters. ".." is False, because no word has two letters. "..." is True, because "bad", "dad" and "mad" have three letters.

Python prints the booleans as True and False, and it prints a list of strings with quotes around each word.

The class has two methods that both walk the trie. search stops at the first match and returns a yes or no answer. find_all visits every branch and collects each matching word. It builds the word in a list of letters called path, which is changed in place. Each time it moves to a child, it appends that letter, and when it returns from that child, it removes the letter with path.pop(). "".join(path) turns the list into a string only when a word is found. That add and remove pattern is called backtracking. It lets one list serve every branch without making a new copy of the word for each one.

In find_all, the dot loops over the index k from 0 to 25 with enumerate. The letter is chr(ord("a") + k). The loop runs in alphabetical order, which is why the output lists "bad" before "bar" and "bay" before "cab".

A second example: a dot in the middle

Take the pattern c.t and the dictionary "cat", "cot", "cut" and "cart". The middle dot can match "a", "o" or "u". The word "cart" is longer, so it cannot match a three-letter pattern.

The search starts at the root. The first letter "c" has one child, so it follows that path. Now the node is "c". The dot tries each child of "c". The children are "a", "o" and "u".

Under "a", the next pattern letter is "t". The node "ca" has a child "t", and that node has its end flag set. The search returns True at this first branch, so the answer for c.t is True. The find_all method would keep going and add "cat", then "cot" from the "o" branch and "cut" from the "u" branch. The word "cart" is never reached, because its path goes from "ca" to "r", and the pattern needs a "t" at that point.

This example shows a point that often surprises beginners. A dot can cost more than a letter, because the search may open several branches. A letter opens one branch at most. A dot opens every branch that exists at that level.

A third example: many dots

Patterns with several dots need more work. The pattern .... matches any four-letter word. The search tries every child at the first level, every child at the second level, and so on. This is a full walk of every branch that is four levels deep.

To see the cost, the next program counts the number of recursive calls for several patterns. It uses the same three words, "bad", "dad" and "mad". It resets the counter before each pattern. The counter is a module-level variable, and the function declares global calls so that it changes that variable.

The output is:

.ad found=True calls=4
b.. found=True calls=4
... found=True calls=4
x.. found=False calls=1
.... found=False calls=10

The pattern x.. costs one call. The root has no child "x", so the search stops at once. The pattern .... costs 10 calls. It tries "b", "d" and "m" at the first level. Under each of them it finds only one child, "a", and then only one child, "d", and then the pattern still has one dot left with no children to try. The search does more work for each extra dot, but it never visits a node twice in this trie, and it never walks past the length of the pattern.

The worst case is a pattern of many dots on a large dictionary. Each dot can open up to 26 branches. The search never visits more nodes than the trie holds, but with several dots it can visit a large share of them. For a big dictionary, test the pattern on realistic input before you rely on it.

Tracing find_all step by step

The find_all call for the pattern ba. on the dictionary "bat", "bay", "bad", "cab" and "bar" shows how the path changes during the walk. Read the trace with the code open beside it.

1. The first pattern character is "b". The root has one child, "b", so the path becomes ["b"].
2. The second pattern character is "a". The node "b" has the child "a", so the path becomes ["b", "a"].
3. The third pattern character is a dot. The node "ba" has four children, and the loop visits them in alphabetical order: "d", "r", "t" and "y".
4. The child "d" is appended, so the path becomes ["b", "a", "d"]. The pattern is used up, and the node has its end flag set, so "bad" goes into the result list. The code then pops the "d", and the path is "ba" again.
5. The child "r" gives "bar", which is also a word, so it goes into the list. The code pops the "r".
6. The child "t" gives "bat", and the child "y" gives "bay". Both are words, so both go into the list.

The result is ['bad', 'bar', 'bat', 'bay']. The word "cab" is not in the result, because its first letter is "c", and the first pattern letter is "b". The search never enters the "c" branch.

The path.pop() call is what makes the list correct. If the code did not remove the "d" after the "bad" branch, the next branch would start from "bad" instead of "ba", and the output would contain words that do not match.

Comparing with a plain list

A simple way to find matches is to check every word in a list. For each word, compare its length with the pattern, then compare each letter, skipping any position where the pattern has a dot. This works, but it does the same work for every word, even when the first letter already rules the word out.

The trie does the work in a different order. It checks a letter once for each node, and a failed letter removes every word that shares that prefix. The dictionary "bad", "dad" and "mad" shows the difference. The pattern x.. fails in the list version only after the code has looked at all three words. In the trie version, the root has no child "x", so the search makes one call and stops. The counting program above shows this as calls=1.

The gap grows as the dictionary grows. A list of one million words is checked one word at a time. A trie with the same words can skip every word that starts with a letter the pattern does not allow. The trie uses more memory, because each node holds 26 child slots in this lesson's code, so the choice is a trade between time and memory.

Common mistakes

The most common mistake is to treat the dot like a normal letter. The code then uses the dot's character code to find a child. A dot has the character code 46, and ord(".") - ord("a") is 46 minus 97, which is -51. A list of 26 slots has no slot -51, so Python raises an error when it reaches the lookup.

The next program has the dot check missing. It uses the exact search for every character, and it runs on the pattern ba and then on b..

class Node:
    def __init__(self):
        self.children = [None] * 26
        self.is_end = False
 
 
def search(node, pattern, i):
    if i == len(pattern):
        return node.is_end
    ch = pattern[i]
    # Bug: no check for ".", so ord(ch) - ord("a") is -51 for a dot
    child = node.children[ord(ch) - ord("a")]
    return child is not None and search(child, pattern, i + 1)
 
 
root = Node()
b = Node()
root.children[ord("b") - ord("a")] = b
b.children[0] = Node()
b.children[0].is_end = True
print(search(root, "ba", 0))
print(search(root, "b.", 0))

The output is:

True
Traceback (most recent call last):
  File "main.py", line 22, in <module>
    print(search(root, "b.", 0))
          ~~~~~~^^^^^^^^^^^^^^^
  File "main.py", line 13, in search
    return child is not None and search(child, pattern, i + 1)
                                 ~~~~~~^^^^^^^^^^^^^^^^^^^^^^^
  File "main.py", line 12, in search
    child = node.children[ord(ch) - ord("a")]
            ~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^
IndexError: list index out of range

The first line is correct. The second line fails, because the list index is -51, and the list has only 26 slots. The fix is the if ch == "." branch in the real code. The file name in the traceback is main.py here, and the path before it depends on where you save the file.

The second mistake is to forget the end flag. The next program returns True as soon as the pattern runs out, even when the node is not the end of a word. The word "ba" is a prefix of "bad", but it is not a word in the dictionary.

class Node:
    def __init__(self):
        self.children = [None] * 26
        self.is_end = False
 
 
def insert(root, word):
    node = root
    for ch in word:
        i = ord(ch) - ord("a")
        if node.children[i] is None:
            node.children[i] = Node()
        node = node.children[i]
    node.is_end = True
 
 
# Bug: returns True whenever the walk reaches the end of the pattern
def search(node, pattern, i):
    if i == len(pattern):
        return True
    ch = pattern[i]
    child = node.children[ord(ch) - ord("a")]
    return child is not None and search(child, pattern, i + 1)
 
 
root = Node()
insert(root, "bad")
print("bad:", search(root, "bad", 0))
print("ba:", search(root, "ba", 0))

The output is:

bad: True
ba: True

The line for "ba" is wrong. The word "ba" is not in the dictionary, and the program says it is. The fix is to return node.is_end at the end of the pattern. The end flag is the only proof that the path spells a whole word.

The third mistake is a wrong index. The code uses the letter itself instead of its offset from "a". Python does not allow a string as a list index, so the mistake shows up as an error at the first letter:

class Node:
    def __init__(self):
        self.children = [None] * 26
        self.is_end = False
 
 
root = Node()
node = root
for ch in "cat":
    # Bug: the letter itself is used as the index
    idx = ch
    if node.children[idx] is None:
        node.children[idx] = Node()
    node = node.children[idx]

The output is:

Traceback (most recent call last):
  File "main.py", line 12, in <module>
    if node.children[idx] is None:
       ~~~~~~~~~~~~~^^^^^
TypeError: list indices must be integers or slices, not str

The fix is ord(ch) - ord("a"). If you write ord(ch) without the subtraction, the mistake is different. The index is 99 for the letter "c", which is far beyond the 26 slots, and Python raises IndexError: list index out of range instead.

The fourth mistake is a missing check for None. The program below reads a field from a child that was never created.

class Node:
    def __init__(self):
        self.children = [None] * 26
        self.is_end = False
 
 
root = Node()
# Bug: no None check before reading the child's field
ends = root.children[ord("x") - ord("a")].is_end
print(ends)

The output is:

Traceback (most recent call last):
  File "main.py", line 9, in <module>
    ends = root.children[ord("x") - ord("a")].is_end
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
AttributeError: 'NoneType' object has no attribute 'is_end'

The slot for "x" is None, because no word starts with "x". Python says the attribute cannot be read from NoneType, which is the type of None. The fix is to test child is not None before reading the field.

Practice

Exercise 1

Here is a dictionary with the words "cat", "cab" and "cart". Predict the result of search("ca.") and search("ca.."). For each one, name a word that makes it true.

Show the answer: Both are True. ca. is true because "cat" and "cab" have three letters and start with "ca". ca.. is true because "cart" has four letters and starts with "ca".

Exercise 2

The dictionary has only "cat". What does search("c.") return, and why?

Show the answer: It returns False. The pattern has two characters and the word has three. The search reaches the end of the pattern at the node "ca" and that node's end flag is False, because "ca" is not a word.

Exercise 3

The dictionary has "bark", "bard" and "cart". Write down the output of find_all("....") in the order the program prints it.

Show the answer: The output is ['bard', 'bark', 'cart']. The search visits the first letter in alphabetical order, so "b" comes before "c". Under "ba", the last letter "d" comes before "k", so "bard" comes before "bark".

Exercise 4

Change find_all so that it returns how many words match, instead of a list of words. Write the new method signature and say what changes in the recursive method.

Show the answer: The method becomes def count(self, pattern), and it returns an integer. The recursive method returns 1 at the end of the pattern if the node has its end flag set, and 0 otherwise. Each branch adds up the values from its children, which sum does for a generator expression. The path list is no longer needed, because the program does not build the words.

Exercise 5

The dictionary has "abc", "adc" and "axe". Predict the output of find_all("a.c"). Explain why "axe" is not in the result.

Show the answer: The output is ['abc', 'adc']. The pattern a.c has three characters, and the last character must be "c". The word "axe" ends in "e", so the search does not match it.

Summary

• A dot in a pattern matches any one letter, so the search must try every child at that level.
• The search stops at the first match when it only needs a yes or no answer, and any does that stop for you.
• Backtracking lets one list serve every branch when the program collects matches.
• The end flag decides whether the walk through the pattern spells a whole word.
• Many dots can open many branches, so the cost grows with the number of matching nodes.