DSA Regular Expression Matching
Regular expression matching checks whether a pattern can cover a whole text. The dot matches any single character, and a star after a character lets that character repeat or vanish.
The problem
Regular expression matching checks whether a pattern can cover a whole text. This pattern language is small. It has literal characters, one wildcard, and one repetition mark.
The dot matches any single character. A star applies to the single character just before it, and that pair may repeat the character any number of times or vanish entirely. Nothing else is special.
The cases used in this article
cases = [
("aa", "a", False),
("aa", "a*", True),
("ab", ".*", True),
("aab", "c*a*b", True),
("mississippi", "mis*is*p*.", False),
]
for text, pattern, expected in cases:
print(repr(text), repr(pattern), "->", expected)The fourth row holds the key surprise. The pair c* matches nothing at all, because the text has no letter c. A star pair is always allowed to vanish.
Intuition: a star pair must repeat at least once is wrong
The first idea reads a star as repetition with a minimum of one. Under that reading, c* in the pattern c*a*b must produce a letter c. The text aab has none, so the idea declares failure.
The real rule allows zero repetitions. A star pair contributes a run of its character, and a run may be empty. Zero is a legal length for every star pair.
The vanishing pair inside c*a*b
text = "aab"
built = "" + "aa" + "b"
print("c* contributes:", repr(""))
print("a* contributes:", repr("aa"))
print("b contributes:", repr("b"))
print("joined:", repr(built), "- equals the text:", built == text)The joined pieces rebuild the text exactly. The empty first piece is not a trick. It is the rule that makes this case pass.
Brute force: branch at every star pair
The brute force reads the pattern from the front. A plain character or a dot consumes one text character. A star pair branches in two directions.
One branch skips the pair entirely. The other branch consumes one matching text character and keeps the pair active. A failing pattern explores both branches at every star.
The branching brute force, counted
calls = 0
def match_brute(text, pattern):
global calls
calls += 1
if not pattern:
return not text
star = len(pattern) > 1 and pattern[1] == "*"
if star:
if match_brute(text, pattern[2:]):
return True
if text and (pattern[0] == "." or pattern[0] == text[0]):
return match_brute(text[1:], pattern)
return False
if text and (pattern[0] == "." or pattern[0] == text[0]):
return match_brute(text[1:], pattern[1:])
return False
for text, pattern in [("aab", "c*a*b"), ("mississippi", "mis*is*p*.")]:
calls = 0
print(repr(text), repr(pattern), "->", match_brute(text, pattern), "calls:", calls)The passing case finishes in 8 calls. The failing case needs 20 calls on an eleven-character text, and star pairs over matching runs grow far worse, as the counted sizes in the Complexity section show. Many calls revisit the same pair of remaining text and remaining pattern, and the table answers each such pair once.
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. The answer sits in the bottom right cell.
A star cell chooses between two readings. Skipping the pair reads the cell two pattern steps back. Consuming one matching character reads the cell above and keeps the star active.
The table on every case
def is_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(2, n + 1):
if pattern[j - 1] == "*":
dp[0][j] = dp[0][j - 2]
for i in range(1, m + 1):
for j in range(1, n + 1):
if pattern[j - 1] == "*":
skip = dp[i][j - 2]
consume = (pattern[j - 2] == "." or pattern[j - 2] == text[i - 1]) and dp[i - 1][j]
dp[i][j] = skip or consume
elif pattern[j - 1] == "." or pattern[j - 1] == text[i - 1]:
dp[i][j] = dp[i - 1][j - 1]
return dp[m][n]
cases = [
("aa", "a", False),
("aa", "a*", True),
("ab", ".*", True),
("aab", "c*a*b", True),
("mississippi", "mis*is*p*.", False),
]
for text, pattern, expected in cases:
result = is_match(text, pattern)
print(repr(text), repr(pattern), "->", result, "expected:", expected, "match:", result == expected)All five cases pass. The empty-text row of the table needs its own rule. It steps two pattern characters at a time, because only whole star pairs can vanish.
Walkthrough: ab against a*b
The walkthrough uses a two-character text. The pattern a*b opens with a star pair. That pair must contribute exactly one a here.
Each row adds one text character. Each column adds one pattern character. The star column is the only column that reads two steps back.
The verdict table for ab and a*b
text, pattern = "ab", "a*b"
m, n = len(text), len(pattern)
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
for j in range(2, n + 1):
if pattern[j - 1] == "*":
dp[0][j] = dp[0][j - 2]
for i in range(1, m + 1):
for j in range(1, n + 1):
if pattern[j - 1] == "*":
skip = dp[i][j - 2]
consume = (pattern[j - 2] == "." or pattern[j - 2] == text[i - 1]) and dp[i - 1][j]
dp[i][j] = skip or consume
elif pattern[j - 1] == "." or pattern[j - 1] == 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 bottom right cell is one, printed as the digit 1. The path through it uses the consume branch exactly once. A second a in the text would use that branch twice.
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 branches at every star pair and repeats subproblems.
The repeat count is the honest measure here. Wall-clock time would hide it on inputs this small. The counts below grow the failing input one star pair at a time.
Branch calls against table cells on failing inputs
calls = 0
def match_brute(text, pattern):
global calls
calls += 1
if not pattern:
return not text
star = len(pattern) > 1 and pattern[1] == "*"
if star:
if match_brute(text, pattern[2:]):
return True
if text and (pattern[0] == "." or pattern[0] == text[0]):
return match_brute(text[1:], pattern)
return False
if text and (pattern[0] == "." or pattern[0] == text[0]):
return match_brute(text[1:], pattern[1:])
return False
for text, pattern in [("aa", "a*a*b"), ("aaaa", "a*a*a*b"), ("aaaaaa", "a*a*a*a*b")]:
calls = 0
match_brute(text, pattern)
print("text length", len(text), "pattern", repr(pattern), "- brute calls:", calls, " table cells:", len(text) * len(pattern))Each added star pair multiplies the branch count. The cell count only grows by the two lengths. That contrast is the whole reason for the table.
Edge cases and pitfalls
An empty text matches a pattern of star pairs only. Every pair must vanish. One plain character in the pattern breaks the match at once.
The classic pitfall treats the star as a standalone wildcard. A star never stands alone in this language. It always binds to the one character before it, so a pattern cell at a star must look two steps back, not one.
Edge cases, run
def is_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(2, n + 1):
if pattern[j - 1] == "*":
dp[0][j] = dp[0][j - 2]
for i in range(1, m + 1):
for j in range(1, n + 1):
if pattern[j - 1] == "*":
skip = dp[i][j - 2]
consume = (pattern[j - 2] == "." or pattern[j - 2] == text[i - 1]) and dp[i - 1][j]
dp[i][j] = skip or consume
elif pattern[j - 1] == "." or pattern[j - 1] == text[i - 1]:
dp[i][j] = dp[i - 1][j - 1]
return dp[m][n]
print("empty text, star pairs:", is_match("", "a*b*"))
print("empty text, one literal:", is_match("", "a"))
print("empty pattern, empty text:", is_match("", ""))
print("dot needs a character:", is_match("", "."))
print("star pair repeats:", is_match("aaa", "a*"))
print("dot star covers all:", is_match("abc", ".*"))The dot row fails against an empty text. A dot consumes exactly one character, like a literal that accepts anything. Only a star pair can consume zero.
Exercise
A table cell sits at a star in the pattern. Which two choices decide it?