Regular expression and wildcard matching in Python

Why this matters

A pattern is a short description of many possible texts. You use patterns when you search a log for lines that start with an error code, when you check that a user name has the right shape, or when a shell turns *.txt into a list of files. Every one of these tools has a matcher inside it. Writing a matcher yourself shows how the text and the pattern move together, one character at a time.

This lesson builds two matchers. The first follows the regular expression rules, where . matches one character and * matches zero or more copies of the character before it. The second follows the wildcard rules used by many file searches, where ? matches one character and * matches any run of characters.

Both matchers fill a two-dimensional table. The grid path lessons earlier in this module use the same kind of table, but there each cell holds a number. Here each cell holds True or False. The next lesson in this module counts how many ways one string appears as a subsequence of another, which also uses a table of numbers. The word break lesson earlier in this module uses a table with one dimension, because it only asks about prefixes of one string.

Python also has both matchers built in. The re module handles regular expressions, and the fnmatch module handles wildcards. On the cases in this lesson, re.fullmatch and fnmatch.fnmatchcase return the same answers as the matchers below. This lesson builds the matchers by hand so that you can see the table.

Every program in this lesson is a complete Python file. Save it as matchers.py and run it with python3 matchers.py. The outputs shown were produced on Python 3.14.4.

Words you need first

A text is the string you test. A pattern is the string of rules you test it against.

A match means the whole text fits the whole pattern. A pattern that matches only part of the text does not count. The text abc does not match the pattern a., even though ab does match it, because the dot takes one character and the c is left over.

Some terms in this lesson have exact meanings:

• A character is one letter, digit or symbol, such as a or 7. Python has no separate character type. A character is a string of length one, so s[0] is a string that holds one letter.
• A dot in a regular expression matches any one character.
• A star in a regular expression applies to the character directly before it. The pair a* means zero or more a characters.
• A wildcard is a simpler pattern language. It uses ? for one character and * for any run of characters, with no character before the star.
• A prefix is the first few characters of a string. The prefix ab is the first two characters of abc.
• A base case is a table cell whose answer you set directly, without using other cells.

The two rule sets look alike, but they are not the same. The table below shows the difference.

A regular expression pattern a* matches the text aaa and the empty text, but not ab. A wildcard pattern a* matches ab and abc, because its star can cover any run after the a. Mixing the two rule sets is a common source of mistakes, so this lesson keeps them apart.

The regular expression rules

Read a regular expression pattern from left to right. Each element is one of three things.

• A letter or digit, which matches the same character in the text. The pattern a matches the text a and nothing else.
• A dot, which matches any one character. The pattern . matches a, z and 7, but not the empty text and not ab.
• A character followed by a star. The pair x* matches zero copies of x, or one copy, or more. The pattern a* matches the empty text, a, aa and aaaa.

Here are some pairs to check your reading.

• ab*c matches ac, abc and abbbc. The star lets the b repeat or disappear.
• .* matches any text at all, including the empty text. The dot takes any character and the star repeats it any number of times.
• a.c matches abc and a7c, but not ac. The dot must take exactly one character.

A star always applies to the single element directly before it. It does not apply to the whole pattern. The pattern ab* means a then zero or more b, not zero or more copies of ab. This is why the text abab does not match ab*.

A valid regular expression pattern never starts with a star, because a star needs an element before it. The examples in this lesson keep that rule. The code in this lesson does not check for a leading star, and the mistakes section shows what happens.

The idea: a table of prefixes

Let s be the text and p be the pattern. Let m be the length of s and n be the length of p.

Define dp[i][j] as True when the first i characters of s match the first j characters of p, and False otherwise. Row i is a text prefix. Column j is a pattern prefix. The answer to the whole question is the cell at the bottom right, dp[m][n].

Before filling any cell, set the base cases.

The cell dp[0][0] is True. An empty text matches an empty pattern, because there is nothing to match.

Column 0 is the empty pattern. A non-empty text cannot match an empty pattern, so dp[i][0] is False for every i above 0. This base case is what stops a text from matching a pattern that has run out.

Row 0 is the empty text. It needs more care. An empty text can match a pattern only when every element in the pattern can match nothing. A letter or a dot must match one character, so it cannot match nothing. A star pair x* can match nothing, because the star allows zero copies. So dp[0][j] is True when the pattern up to column j is made only of star pairs.

Take the pattern a*. The empty text matches it, because the a* pair matches zero copies. The pattern a does not match the empty text, because the a must match one character. So for the text `` (empty), the row reads: empty pattern is True, pattern a is False, pattern a* is True.

This is the empty-text base. Many wrong answers in matchers come from skipping it. The mistakes section shows the exact wrong output.

The three cases for each cell

For the cell dp[i][j], the last element of the pattern prefix is p[j - 1], and the last character of the text prefix is s[i - 1]. Python strings start at index 0, so the table index is one more than the string index. That is why the code writes j - 1 and i - 1.

There are three cases. Only one of them needs a special rule.

Case 1: the pattern element is a letter or a dot. This element matches exactly one text character. The cell is True only when the last text character matches the element, and the cell diagonally up and to the left is True. Diagonal means the text prefix and the pattern prefix both shrink by one.

if pattern element is '.' or equals the last text character:
    dp[i][j] = dp[i - 1][j - 1]
else:
    dp[i][j] = False

Case 2: the pattern element is a star. The star applies to the element before it. Call that element prev, at position j - 2. A star has two ways to match.

• Zero copies. The pair prev* vanishes from the pattern. The text prefix must then match the pattern prefix two columns back, which is dp[i][j - 2].
• One or more copies. If prev matches the last text character, the star can absorb that character and stay in the same place in the pattern. The text prefix shrinks by one, and the pattern prefix stays the same, which is dp[i - 1][j].

So the rule for a star cell is:

dp[i][j] = dp[i][j - 2]
           OR (prev matches s[i - 1] AND dp[i - 1][j])

The second part is the one that is easy to miss. It says a star can keep taking characters while the text still matches its element. For the text aaa and the pattern a*, the cell for aa and a* is True because the star took the second a and the cell for a and a* is True.

Case 3: a column for an empty pattern prefix, or a row for an empty text prefix. These are the base cases from the previous section. They are set before the main loop starts, so the main loop never reads a cell that has not been set.

Worked example 1: aa against a*

The text is aa and the pattern is a*. So m is 2 and n is 2. The table has three rows and three columns. Each row is a text prefix and each column is a pattern prefix.

Start with the base cases. Row empty and column empty are filled. The cell dp[0][0] is True. The cell for the empty text and the pattern a* uses Case 2 with zero copies: dp[0][0] is True, so the cell is True.

Now fill row a, which is the text prefix a.

• The column a is a letter. The text character a matches it, and dp[0][0] is True. The cell is True.
• The column a* is a star pair. Zero copies gives dp[1][0], which is False because a text of one character cannot match an empty pattern. One or more copies needs a to match the last text character a, which it does, and then dp[0][2] is True. The cell is True.

Now fill row aa.

• The column a is a letter. The last text character is a, which matches. The cell diagonally up and left is dp[1][0], which is False. The cell is False, because the text has two characters and the pattern element only takes one.
• The column a* is a star pair. Zero copies gives dp[2][0], which is False. One or more copies needs a to match the last text character, which it does, and then dp[1][2] must be True. Row a, column a* was True. The cell is True.

The bottom right cell is True, so the text aa matches the pattern a*.

Read the table from top to bottom. The column a* is true in every row from the empty text downward. That is what it means for a star to repeat its element any number of times.

Worked example 2: aab against c*a*b

This example has two star pairs. The first is c*, which can match zero copies of c. The second is a*, which can match one or more a characters. The text is aab.

The program below prints the full table for this input. The table has four rows, for the empty text and the three characters of aab. It has six columns, for the empty pattern and each of the five characters of c*a*b.

         ''   c   *   a   *   b
   ''     T   F   T   F   T   F
    a     F   F   F   T   T   F
    a     F   F   F   F   T   F
    b     F   F   F   F   F   T

Read the first row. The empty text matches the empty pattern, so the first cell is T. It matches c*, which can take zero copies of c, so the third column is T. It matches c*a*, which takes zero copies of both pairs, so the fifth column is T. It does not match c alone, so the second column is F.

Read the second row, which is the text a. The cell for c*a is true, because c* takes zero copies and a matches the text. The cell for c*a* is also true, because a* takes one copy of a in the same way. The cell for c*a*b is false, because the text has no b yet.

Read the last row. The text is aab, and the last character b matches the last element of the pattern. The cell diagonally up and left is true, because aa matches c*a*. So the bottom right cell is true, and aab matches c*a*b.

The table makes one point clear. Each star pair changes the table in the same way. The star pair gives a true cell through zero copies, which copies the value two columns back, and through one or more copies, which copies the value one row up.

Worked example 3: wildcard rules

Now the wildcard rules. The symbol ? matches any one character. The symbol * stands alone. It does not need a character before it, and it matches any run of characters, including the empty run.

The cases change in two places.

• A ? or a matching letter works like a dot in the regular expression rules. The cell is dp[i - 1][j - 1].
• A * has two choices. It matches the empty run, which copies the cell to its left, dp[i][j - 1]. Or it takes the last text character and stays in place, which copies the cell above, dp[i - 1][j]. So the rule is dp[i][j] = dp[i][j - 1] OR dp[i - 1][j].

Notice that the star reads j - 1, not j - 2. There is no element before the star to skip. Using j - 2 here is a common mistake, and the mistakes section shows it.

Here are two short checks. The pattern ?a matches ca, because ? takes c and a matches a. The text cb does not match ?a, because ? takes c and then a must match b, which fails.

The text adceb matches the pattern *a*b as follows. The first star matches the empty run. The letter a matches the first character of the text. The second star matches the run dce. The letter b matches the last character. Every part of the text is used, so the match holds.

The text acdcb does not match a*c?b. After the first a, the rest of the text is cdcb. The pattern needs the last three characters of the text to be c, then any one character, then b. The last three characters are dcb, and the first of them is d, not c. No choice of star run can fix that, so the answer is false.

The Python program

The program below contains one table builder, the two matchers built on it, a table printer and a few checks. regex_table fills the table. It takes a with_base flag so that the mistakes section can turn off the empty-text base and show the result. is_match and is_match_no_base read the answer from the bottom right cell of that table.

The if __name__ == "__main__": line means the checks run only when you run the file directly. If another file imports matchers, the checks do not run.

In Python, dp[i][j] = dp[i][j] or dp[i - 1][j] looks like it reads the cell it writes. That is intended. The first line of the star case sets the cell to its zero-copies value, and the second line adds the one-or-more value with or. Both operands are True or False, so the result is too. A cell that is already True stays True.

Run it with python3 matchers.py. The output below was produced by that exact file.

regex (. and *):
  is_match("aa", "a") = False
  is_match("aa", "a*") = True
  is_match("ab", ".*") = True
  is_match("aab", "c*a*b") = True
  is_match("mississippi", "mis*is*p*.") = False
  is_match("", "a*") = True
  is_match("", "a") = False
  is_match("abc", "a.c") = True
  is_match("aaa", "a*a") = True
 
table for aab vs c*a*b:
         ''   c   *   a   *   b
   ''     T   F   T   F   T   F
    a     F   F   F   T   T   F
    a     F   F   F   F   T   F
    b     F   F   F   F   F   T
 
missing base, is_match("", "a*") = False
with base,    is_match("", "a*") = True
 
wildcard (? and *):
  wildcard_match("aa", "*") = True
  wildcard_match("adceb", "*a*b") = True
  wildcard_match("cb", "?a") = False
  wildcard_match("acdcb", "a*c?b") = False
  wildcard_match("", "*") = True
  wildcard_match("", "?") = False

Common mistakes

Leaving out the empty-text base. Here the base loop is skipped, so the row for the empty text is never filled. The output shows the damage.

missing base, is_match("", "a*") = False
with base,    is_match("", "a*") = True

The text is empty and the pattern a* should match, because the star takes zero copies. Without the base loop, the cell dp[0][2] keeps its starting value of False. The fix is the loop that starts at j = 2 and copies the value two columns back for each star pair. A useful check is to run the matcher on an empty text and a pattern made of star pairs, because that exposes a missing base at once.

Starting a pattern with a star. The pattern * has no element before the star. The code reads dp[i][j - 2] with j equal to 1, so the index is -1. In Java that index is an error. In Python it is not. A negative index counts from the end of the list, so dp[i][-1] is the last cell of the row, and p[-1] is the last character of the pattern. Nothing raises an error, and the answer is simply wrong.

print(is_match("a", "*"))

This prints False, with no message. A pattern that starts with a star is not valid input for regular expressions, so the matcher should refuse it. Add this check at the top of is_match:

if p.startswith("*"):
    raise ValueError("pattern starts with *")

With the check in place, the same call stops with an error. The first lines of the traceback are shortened here.

Traceback (most recent call last):
  ...
    raise ValueError("pattern starts with *")
ValueError: pattern starts with *

The wildcard rules allow a leading star, so the wildcard matcher does not use this check.

Mixing the two rule sets. The regular expression a* matches the empty text, a and aaa, but not ab. The wildcard a* matches ab, because the star covers the b. If a matcher uses the wildcard rule on a regular expression pattern, it gives answers that look plausible and are wrong for the regular expression. The rule is simple. Look at what * follows. In a regular expression it follows a character. In a wildcard it stands alone.

Running both matchers on the same input shows the difference.

print(is_match("ab", "a*"), wildcard_match("ab", "a*"))

False True

Using j - 2 in the wildcard matcher. In the wildcard rules the star has no element before it, so the zero-copies case reads dp[i][j - 1]. Copying the regular expression code into the wildcard matcher and keeping j - 2 does not raise an error in Python. For j equal to 1 it reads the last cell of the row, and for j equal to 2 it reads the cell two columns back, which is the wrong column for a wildcard. The answers look like normal True and False values, so the mistake is easy to miss. Test the matcher on a case you can check by hand, such as wildcard_match("", "*"), which must be True.

Building the table with one shared list. A common way to make a table is [[False] * (n + 1)] * (m + 1). It looks right, but it makes every row the same list object. Setting one cell then changes the same column in every row.

rows = [[False] * 3] * 3
rows[0][0] = True
print(rows)

[[True, False, False], [True, False, False], [True, False, False]]

The fix is a list comprehension, which builds a new inner list for each row:

dp = [[False] * (n + 1) for _ in range(m + 1)]

Practice

Predict each answer on paper before you check it. The answers say which rule decides the result.

Exercise 1. What does is_match("ab", ".*c") return?

Show the answer

It returns False. The pattern ends with c, so the last character of the text must be c. The text ab ends with b, so the last part of the match fails. The .* part can take any run, but it cannot make the final c appear.

Exercise 2. What does wildcard_match("", "**") return?

Show the answer

It returns True. Each * in the wildcard rules can match the empty run, and two empty runs together still make an empty text. Both stars copy the value from the cell to their left, which starts at the True base cell.

Exercise 3. What does is_match("aaa", "ab*a*c*a") return?

Show the answer

It returns True. The first a matches the first character of the text. The pair b* takes zero copies. The pair a* takes the second a. The pair c* takes zero copies. The final a matches the third character. Every character of the text is used, in the order the pattern allows.

Exercise 4. Which prefixes of the pattern a*b*c match the empty text? List them.

Show the answer

The prefixes empty, a* and a*b* match the empty text. Each star pair can take zero copies, so a* and a*b* both match the empty text. The prefix a*b*c does not, because the letter c must match one character. Check it with is_match("", "a*b*"), which returns True, and is_match("", "a*b*c"), which returns False.

Exercise 5. Fill in the empty-text row for the pattern x*y in a table, then say what is_match("y", "x*y") returns.

Show the answer

Read across the pattern prefixes empty, x, x* and x*y. The empty-text row is T F T F. The prefix x* is True, because the star takes zero copies of x. The prefix x*y is False, because the letter y cannot match nothing. The text y matches x*y, because the star takes zero copies and the letter y matches the text. The answer is True. Running is_match("y", "x*y") returns True.

Summary

• A regular expression star applies to the one element before it. A wildcard star stands alone and can match any run.
• The table cell dp[i][j] answers whether a text prefix matches a pattern prefix, and the answer is the bottom right cell.
• A letter or dot cell copies the cell diagonally up and left, when the characters match.
• A regular expression star cell copies two columns back for zero copies, and copies the cell above for one or more copies.
• The empty-text row and the empty-pattern column must be set before the main loop runs, or the empty text matches the wrong patterns.
• Python does not stop a negative index, so a leading star gives a quiet wrong answer unless the code checks for it.