0010_regular_expression_matching.py

"""10. Regular Expression Matching  —  Hard

LeetCode: https://leetcode.com/problems/regular-expression-matching/

Problem
-------
Given an input string ``s`` and a pattern ``p``, implement regular expression
matching supporting '.' (matches any single character) and '*' (matches zero or
more of the preceding element).  The match must cover the entire string.

Examples
--------
    Input:  s = "aa", p = "a"
    Output: False   (pattern doesn't cover whole string)

    Input:  s = "aa", p = "a*"
    Output: True    ('a*' matches zero or more 'a' → "aa")

    Input:  s = "ab", p = ".*"
    Output: True    ('.*' matches any sequence)

    Input:  s = "aab", p = "c*a*b"
    Output: True    ('c*' = zero c's, 'a*' = two a's, 'b' = 'b')

Intuition
---------
The '*' operator is the crux.  It must always be paired with its preceding
character (call it X).  When we encounter "X*" in the pattern we have two
exclusive choices:
  1. Use zero copies of X  → skip "X*" entirely (advance pattern by 2).
  2. Use one or more copies → keep "X*" in the pattern but advance the string
     by one (only if the current string character matches X or X is '.').

Build a 2-D boolean DP table where dp[i][j] = True iff s[0:i] matches p[0:j].

Approach
--------
State:
  dp[i][j] = does s[0:i] match p[0:j]?

Recurrence:
  Case A — p[j-1] is a literal letter or '.':
    dp[i][j] = dp[i-1][j-1]  AND  (p[j-1] == s[i-1] or p[j-1] == '.')

  Case B — p[j-1] is '*' (always preceded by p[j-2]):
    sub-case B1 (zero occurrences of p[j-2]):
      dp[i][j] |= dp[i][j-2]          # skip the "X*" pair
    sub-case B2 (one or more occurrences, only if s[i-1] matches p[j-2]):
      if p[j-2] == s[i-1] or p[j-2] == '.':
          dp[i][j] |= dp[i-1][j]      # consume one matching char from s

Base cases:
  dp[0][0] = True   (empty string matches empty pattern)
  dp[i][0] = False  for i > 0  (non-empty string never matches empty pattern)
  dp[0][j]: only "X*X*…" type patterns can match the empty string.
    For each j: if p[j-1] == '*', dp[0][j] = dp[0][j-2].

Complexity
----------
Time:  O(m × n)   fill m × n table (m = len(s), n = len(p)).
Space: O(m × n)   the DP table (can be reduced to O(n) with rolling row).

Edge cases
----------
- Empty string with pattern like "a*b*" → True.
- Pattern longer than string, e.g., ".*" always matches anything.
- Consecutive stars are not valid regex (problem guarantees no such input).

Pattern: Dynamic Programming — 2-D string matching.
ML relevance: Pattern matching is foundational to tokenisers, NLP pre-processing
pipelines, and rule-based data-cleaning steps in ML feature engineering.
"""
from __future__ import annotations


class Solution:
    """LeetCode submission class."""

    def isMatch(self, s: str, p: str) -> bool:
        """Return True iff s matches regex pattern p (supports '.' and '*')."""
        m, n = len(s), len(p)

        # dp[i][j] = True iff s[0:i] matches p[0:j]
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[0][0] = True

        # Empty string can match patterns like a*, a*b*, a*b*c* …
        for j in range(2, n + 1):
            if p[j - 1] == '*':
                dp[0][j] = dp[0][j - 2]   # zero occurrences of p[j-2]

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if p[j - 1] == '*':
                    # B1: zero occurrences — skip the X* pair
                    dp[i][j] = dp[i][j - 2]
                    # B2: one or more occurrences — current s char must match X
                    if p[j - 2] == s[i - 1] or p[j - 2] == '.':
                        dp[i][j] = dp[i][j] or dp[i - 1][j]
                elif p[j - 1] == '.' or p[j - 1] == s[i - 1]:
                    # A: direct match (literal or wildcard '.')
                    dp[i][j] = dp[i - 1][j - 1]
                # else: dp[i][j] remains False

        return dp[m][n]


def _demo() -> None:
    """Run the worked examples as assertions."""
    solver = Solution()

    assert solver.isMatch("aa", "a") is False
    assert solver.isMatch("aa", "a*") is True
    assert solver.isMatch("ab", ".*") is True
    assert solver.isMatch("aab", "c*a*b") is True
    assert solver.isMatch("", "") is True
    assert solver.isMatch("", "a*") is True
    assert solver.isMatch("", "a*b*") is True
    assert solver.isMatch("a", "ab*") is True   # 'b*' = zero b's
    assert solver.isMatch("mississippi", "mis*is*p*.") is False
    assert solver.isMatch("mississippi", "mis*is*ip*.") is True
    print("All tests passed.")


if __name__ == "__main__":
    _demo()