DSA Wildcard Matching
Wildcard matching checks whether a pattern with two special characters can cover a whole text. The character ? covers any single character, and the character * covers any run of characters including none.
The problem
Wildcard matching checks whether a pattern can cover a whole text. The pattern holds literal characters and two special characters.
The character ? covers any single character. The character * covers any run of characters, including an empty run. The whole text must be covered, with nothing left over.
The cases used in this article
cases = [
("aa", "a", False),
("aa", "*", True),
("cb", "?a", False),
("adceb", "*a*b", True),
("acdcb", "a*c?b", False),
]
for text, pattern, expected in cases:
print(repr(text), repr(pattern), "->", expected)The first row fails on length alone. One literal cannot cover two characters. No special character is present to absorb the extra one.
Intuition: covering a star by guessing zero fails
The first idea handles literals and question marks position by position. It meets a star and must decide how much text the star covers. Guessing zero is the simple choice.
That guess fails whenever the star must absorb something. The star in the pattern *a*b must cover the opening run before the letter a. Zero coverage leaves the text misaligned from the first step.
A star forced to cover nothing
def match_star_empty(text, pattern):
# a star covers nothing; ? covers one character; literals match themselves
t = 0
for p in pattern:
if p == "*":
continue
if t >= len(text):
return False
if p != "?" and p != text[t]:
return False
t += 1
return t == len(text)
print("adceb vs *a*b with empty stars:", match_star_empty("adceb", "*a*b"))
print("aa vs * with empty star:", match_star_empty("aa", "*"))
print("both verdicts should be True")Both verdicts come out wrong. A star has a whole range of possible coverages. Any fixed guess fails on some input, so the coverage must stay open.
Brute force: try every coverage for every star
The brute force works through the text and the pattern together. A literal or a question mark consumes one character from each. A star branches over every coverage from zero up to the rest of the text.
Each branch continues the match from a new position. Branches multiply at every star. A failing pattern explores the whole tree before answering.
The branching brute force, counted
calls = 0
def match_brute(text, pattern):
global calls
calls += 1
if not pattern:
return not text
p = pattern[0]
if p == "*":
for take in range(len(text) + 1):
if match_brute(text[take:], pattern[1:]):
return True
return False
if not text:
return False
if p == "?" or p == text[0]:
return match_brute(text[1:], pattern[1:])
return False
for text, pattern in [("adceb", "*a*b"), ("acdcb", "a*c?b")]:
calls = 0
print(repr(text), repr(pattern), "->", match_brute(text, pattern), "calls:", calls)The failing case explores more branches than the passing one, 11 calls against 8 on these short inputs. Success can stop early. Failure must exhaust every coverage of every star.
The optimal solution: a table of prefix verdicts
The state dp[i][j] says whether the first i text characters match the first j pattern characters in full. A true or false value is the whole state.
A star cell is true when the star covers nothing more, read from the left, or covers one more character, read from above. A literal or question mark cell copies the diagonal when the characters fit. The bottom right cell is the verdict.
The table on every case
def table_match(text, pattern):
m, n = len(text), len(pattern)
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
for j in range(1, n + 1):
if pattern[j - 1] == "*":
dp[0][j] = dp[0][j - 1]
for i in range(1, m + 1):
for j in range(1, n + 1):
p = pattern[j - 1]
if p == "*":
dp[i][j] = dp[i][j - 1] or dp[i - 1][j]
elif p == "?" or p == text[i - 1]:
dp[i][j] = dp[i - 1][j - 1]
return dp[m][n]
cases = [
("aa", "a", False),
("aa", "*", True),
("cb", "?a", False),
("adceb", "*a*b", True),
("acdcb", "a*c?b", False),
]
for text, pattern, expected in cases:
result = table_match(text, pattern)
print(repr(text), repr(pattern), "->", result, "expected:", expected, "match:", result == expected)All five cases pass. The table tries every star coverage at once, encoded in its cells. No coverage is ever guessed or fixed early.
Walkthrough: ad against a*d
The walkthrough uses a text of two characters and a pattern of three. The star sits in the middle. It must cover nothing, because both letters are already matched by literals.
The first row handles an empty text. Only a leading run of stars keeps it true. Every later row adds one text character.
The verdict table for ad and a*d
text, pattern = "ad", "a*d"
m, n = len(text), len(pattern)
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
for j in range(1, n + 1):
if pattern[j - 1] == "*":
dp[0][j] = dp[0][j - 1]
for i in range(1, m + 1):
for j in range(1, n + 1):
p = pattern[j - 1]
if p == "*":
dp[i][j] = dp[i][j - 1] or dp[i - 1][j]
elif p == "?" or p == text[i - 1]:
dp[i][j] = dp[i - 1][j - 1]
for row in dp:
print([1 if cell else 0 for cell in row])
print("verdict:", dp[m][n])The final row ends in one, printed here as the digit 1. That path runs through the star cell with the star covering nothing. A longer middle run would travel down the star column instead.
Complexity
The table fills one cell per pair of prefixes, so its time and space are O(m times n) for text length m and pattern length n. The brute force multiplies its branches at every star.
A greedy scan also solves this problem in one pass with constant extra memory. It remembers the last star and retries from it with one more covered character. The table stays in this article because its verdicts are easier to inspect.
Branch calls against table cells
calls = 0
def match_brute(text, pattern):
global calls
calls += 1
if not pattern:
return not text
p = pattern[0]
if p == "*":
for take in range(len(text) + 1):
if match_brute(text[take:], pattern[1:]):
return True
return False
if not text:
return False
if p == "?" or p == text[0]:
return match_brute(text[1:], pattern[1:])
return False
for text, pattern in [("aaaa", "*a*a*b"), ("aaaaaaaa", "*a*a*a*b")]:
calls = 0
match_brute(text, pattern)
print("text length", len(text), "- brute calls:", calls, " table cells:", len(text) * len(pattern))The brute call count jumps sharply when one more star joins the pattern. The cell count only grows with the two lengths. Repeated subproblems explain the gap, as in the other table lessons.
Edge cases and pitfalls
An empty text can still match. The pattern must then consist of stars only. Each star covers the empty run, and any literal or question mark breaks the match.
The classic pitfall lets a star match only non-empty runs. That single change breaks the simplest passing row, the text ad against the pattern a*d.
Edge cases, run
def table_match(text, pattern):
m, n = len(text), len(pattern)
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
for j in range(1, n + 1):
if pattern[j - 1] == "*":
dp[0][j] = dp[0][j - 1]
for i in range(1, m + 1):
for j in range(1, n + 1):
p = pattern[j - 1]
if p == "*":
dp[i][j] = dp[i][j - 1] or dp[i - 1][j]
elif p == "?" or p == text[i - 1]:
dp[i][j] = dp[i - 1][j - 1]
return dp[m][n]
print("empty text, only stars:", table_match("", "***"))
print("empty text, one literal:", table_match("", "a"))
print("empty text, question mark:", table_match("", "?"))
print("star covers nothing:", table_match("ad", "a*d"))
print("question mark needs one:", table_match("a", "??"))
print("trailing star:", table_match("abc", "abc*"))The question mark row fails on length. A question mark always consumes exactly one character. It never shrinks to zero the way a star can.
Exercise
A mismatch occurs after a star was seen. What does the greedy scan do?