10. Regular Expression Matching

Problem¶

Determine whether pattern p matches all of string s, where . matches any one character and * repeats the preceding element zero or more times.

s = "aab", p = "c*a*b"
result = True
match: c* -> "", a* -> "aa", b -> "b"

Key trick¶

Use dynamic programming: dp[i][j] records whether s[:i] matches p[:j]; for x*, either ignore the pair or consume one matching character while keeping the same pattern.

Trap¶

* modifies the preceding element; it is not an independent wildcard.
A greedy choice may need to be reversed, so one-pass matching with a single backtracking position is insufficient.
Patterns such as a*b* can match an empty string.
The match must cover the entire string, not only a prefix.

Why is it interesting?¶

It turns ambiguous regex choices into two precise DP transitions and tests careful handling of empty matches.

Python solution¶

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[0][0] = True

        # Each x* pair can represent zero occurrences.
        for j in range(2, n + 1):
            if p[j - 1] == "*":
                dp[0][j] = dp[0][j - 2]

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if p[j - 1] == "*":
                    # Either skip x* or consume one character and keep x*.
                    atom_matches = p[j - 2] == "." or p[j - 2] == s[i - 1]
                    dp[i][j] = dp[i][j - 2] or (atom_matches and dp[i - 1][j])
                else:
                    # A normal atom consumes exactly one character.
                    atom_matches = p[j - 1] == "." or p[j - 1] == s[i - 1]
                    dp[i][j] = atom_matches and dp[i - 1][j - 1]

        return dp[m][n]

Time complexity: \(O(mn)\)
Space complexity: \(O(mn)\)

Comment on my solution¶

The approach resembles greedy wildcard matching, but regex * is tied to its preceding element and creates multiple choices that cannot be represented by one star_idx.

Only the most recent star is remembered, so earlier alternatives cannot be reconsidered.
Consuming a matching literal before processing its following * commits to a choice too early.
After the string is exhausted, the code skips only standalone * characters instead of nullable pairs such as the remaining b* in s = "a", p = "ab*".

# Ideas:
# - One pass while keeping * index match such that we can backtrack
#   and try to match more characters
#

# Wrong Answer: 285/354 testcases passed
# "aab", "c*a*b"
# output: False
# expected: True
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        # "aa", "a"  -> False
        # "aa", "a*" -> True
        # "ab", ".*" -> True
        i = j = 0

        star_idx = -1

        while i < len(s):
            if j < len(p) and p[j] == s[i]:
                i += 1
                j += 1
            elif j < len(p) and p[j] == ".":
                i += 1
                j +=1
            elif j < len(p) and p[j] == "*":
                star_idx = j
                j += 1
            elif star_idx != -1:
                if p[star_idx - 1] == ".":
                    i += 1
                elif p[star_idx - 1] == s[i]:
                    i += 1
                else:
                    return False
            else:
                return False

        while j < len(p) and p[j] == "*":
            j += 1

        return i == len(s) and j == len(p)

# Wrong Answer: 297 / 354 testcases passed
# "mississippi", "mis*is*ip*."
# output: False
# expected: True
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        # "aa", "a"  -> False
        # "aa", "a*" -> True
        # "ab", ".*" -> True
        i = j = 0

        star_idx = -1

        while i < len(s):
            if j < len(p) and p[j] == s[i]:
                i += 1
                j += 1
            elif j < len(p) and p[j] == ".":
                i += 1
                j +=1
            elif j < len(p) and p[j] == "*":
                star_idx = j
                j += 1
            elif j < len(p) - 1 and p[j + 1] == "*":
                star_idx = j + 1
                j += 2
            elif star_idx != -1:
                if p[star_idx - 1] == ".":
                    i += 1
                elif p[star_idx - 1] == s[i]:
                    i += 1
                else:
                    return False
            else:
                return False

        while j < len(p) and p[j] == "*":
            j += 1

        return i == len(s) and j == len(p)