Pattern Matching -- Inventing Wildcards and Regular Expressions

Write match_exact(pat, text) that returns True only when the pattern and the text are exactly the same -- without using == on whole strings. Compare one character at a time.

Why the restriction? Because in a moment some pattern characters will stop meaning themselves -- and then whole-string == is useless. Build the loop (or recursion) now, while the problem is easy.

Think recursively: two strings match if their first characters match and the rest of them match. What are the base cases?

match_exact("abc", "abc")    # True
match_exact("abc", "abd")    # False
match_exact("abc", "abcd")   # False
match_exact("", "")          # True

New rule: in the pattern, ? matches exactly one character -- any character.

a?  matches: a1, a2, aa, ax
a?  does not match: a, abc

Write match_q(pat, text). It is match_exact with one extra case: when the first pattern character is ?, what should you compare -- and what do you recurse on?

match_q("a?c", "abc")    # True
match_q("a?c", "axc")    # True
match_q("a?c", "ac")     # False
match_q("???", "xyz")    # True

The big one: * matches zero or more characters -- any characters.

a*     matches: a, ab, abc, ax
a*b    matches: ab, axyzb, a123b
a*b*c  matches: abc, abbbc, a1b1c
aa?b*  matches: aa1b, aaxby, aa1bcdeffgshshshsh
aa?b*  does not match: aab, ab

Pattern a*b, text "axyzb". The a matches. Now the pattern says * and the text says "xyzb". How many characters should the * swallow?

You cannot know yet -- it depends on what comes after the star. So don't decide. Try both options and let recursion explore:

1. The * swallows nothing --> try matching the rest of the pattern (b) against "xyzb".
2. The * swallows one more character --> the star stays, try *b against "yzb".

If either branch succeeds, the match succeeds. What is the base case when the text runs out but the pattern is "*"?

Write match(pat, text) supporting literals, ?, and *.

Your match is exactly what the shell does with filenames (called globbing).

Write find_matching(pattern, names) that returns all names matching the pattern.

files = ["report.txt", "report.pdf", "data1.csv", "data2.csv", "notes.txt", "img.png"]
find_matching("*.txt", files)      # ["report.txt", "notes.txt"]
find_matching("data?.csv", files)  # ["data1.csv", "data2.csv"]
find_matching("report.*", files)   # ["report.txt", "report.pdf"]

The pattern a*b is matched against the string axxbyyb. The * is greedy -- it first tries to consume as many characters as possible. Why does the matcher need backtracking to find the correct match?

A. Because `*` can only match letters, not `x` or `y`

B. The greedy `*` initially consumes `xxbyyb`, but then the final `b` in the pattern has nothing left to match -- so the matcher must back up and try consuming fewer characters

C. Backtracking is needed because the string contains duplicate `b` characters

D. The pattern is invalid -- `*` must be at the end

What you invented is the core idea behind regular expressions -- a pattern language so useful it is built into every programming language. Python's re module speaks a richer dialect:

.        any single character            (your ?)
*        previous thing, 0 or more times (your * -- but attached to what precedes it!)
+        previous thing, 1 or more times
[aeiou]  any ONE character from the set
[0-9]    any ONE digit (ranges work)
[^xyz]   any ONE character NOT in the set
{4}      previous thing, exactly 4 times
\.       a literal dot (backslash = escape)
^  $     start / end of the line

Note the twist: regex * means "repeat the previous item" -- so ab*c matches ac, abc, abbbc. Your glob-style a*b is written a.*b in regex.

The two functions you need:

import re
re.search(pattern, text)    # a match object if found anywhere in text, else None
re.findall(pattern, text)   # list of every match in the text

Run this quick demo to see re.search and re.findall in action.

Dates appear as 05/07/1980 or 05-07-1980 (day, month, year -- separator is / or -).

Write a regex string DATE_PATTERN so that re.search(DATE_PATTERN, line) finds dates. Start simple: two digits, a separator, two digits, a separator, four digits.

re.search(DATE_PATTERN, "Date: 05/07/1980")   # found
re.search(DATE_PATTERN, "Date: 05-07-1980")   # found
re.search(DATE_PATTERN, "hello world")        # None

Your pattern happily matches 99/88/1980. Tighten it:

• Day 01--31: can you express it as alternatives? 0[1-9] covers 01--09, [12][0-9] covers 10--29... what covers 30 and 31? Join alternatives with |.
• Month 01--12: same game.

Group alternatives in parentheses: (0[1-9]|...).

Write STRICT_DATE that matches valid day/month combinations only.

is_valid_date("05/07/1980")   # True
is_valid_date("99/07/1980")   # False   (day 99)
is_valid_date("05/19/1980")   # False   (month 19)
is_valid_date("00/04/1980")   # False   (day 00)

(Don't chase February 30th -- even real-world validators leave calendar logic out of regex.)

A security audit: find credit-card-like numbers (four groups of 4 digits, separated by spaces, dashes, or nothing) leaking into text.

Write find_card_numbers(text) returning the list of matches.

find_card_numbers("cc: 1234-4567-8909-1111 and 1234 4567 8909 1111 and 1234456789091111")
# ["1234-4567-8909-1111", "1234 4567 8909 1111", "1234456789091111"]

Hint: a group-plus-separator is [0-9]{4}[- ]? -- how many times does it repeat?

Write find_emails(text) that extracts things shaped like email addresses: one-or-more "word characters" (letters, digits, ., _), then @, then a domain with at least one dot.

find_emails("Contact sandeep@example.com or admin.team@my-site.org today")
# ["sandeep@example.com", "admin.team@my-site.org"]

(A regex that matches every legal email is famously monstrous -- the pragmatic version you are writing is what real codebases actually use.)

Below are genuine lines from an Apache web-server access log (access.log.41 -- 5 MB of real traffic from a Hadoop training site). Each line may contain URLs in the user-agent or referrer fields.

1. Write find_urls(text) that extracts every http://... or https://... URL. Look closely at the lines: a URL ends where whitespace, a quote ", or a closing parenthesis ) begins -- a negated set [^...] handles all three.
2. Run it over LOG_LINES and count which domain appears most (your group_by / word-count instincts from the Dictionaries chapter apply).

Part A -- find_urls:

Part B -- domain_counts:

Write domain_counts(urls) that extracts the domain from each URL and counts how many times each domain appears.

Given the HTML string <b>hello</b> and <b>world</b>, what does the regex <b>.*</b> match?

A. Just `hello`

B. Both `hello` and `world` as two separate matches

C. The entire string `hello and world` as one match, because `.*` is greedy

D. Nothing -- the regex is invalid

What you just invented: The branching trick in your * matcher -- try both, succeed if either succeeds -- is called backtracking. It is the same idea that solves mazes, Sudoku, and the N-Queens problem, and it is exactly how simple regex engines are implemented.