"""
p72 — Regular Expression Matching (LeetCode 10, HARD).

Supports . (any single char) and * (zero or more of preceding element).
Match must be FULL (not substring).

dp[i][j] = True iff s[:i] matches p[:j].

Recurrence:
  If p[j-1] is '*':
      dp[i][j] = dp[i][j-2]                            # match zero of p[j-2]
              or (matches(s[i-1], p[j-2]) and dp[i-1][j])  # match one MORE
  Else:
      dp[i][j] = dp[i-1][j-1] and matches(s[i-1], p[j-1])

where matches(c, pc) = (pc == '.' or pc == c).
"""
from __future__ import annotations
import random
from functools import lru_cache


def _matches(c: str, pc: str) -> bool:
    return pc == "." or pc == c


def is_match_dp(s: str, p: str) -> bool:
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True
    # INVARIANT init row: empty s matches a*b*c* style prefixes.
    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] == "*":
                # zero of preceding
                dp[i][j] = dp[i][j - 2]
                # one more of preceding
                if _matches(s[i - 1], p[j - 2]):
                    dp[i][j] = dp[i][j] or dp[i - 1][j]
            else:
                if _matches(s[i - 1], p[j - 1]):
                    dp[i][j] = dp[i - 1][j - 1]
    return dp[m][n]


def is_match_memo(s: str, p: str) -> bool:
    @lru_cache(maxsize=None)
    def solve(i: int, j: int) -> bool:
        if j == len(p):
            return i == len(s)
        first_match = i < len(s) and _matches(s[i], p[j])
        if j + 1 < len(p) and p[j + 1] == "*":
            return solve(i, j + 2) or (first_match and solve(i + 1, j))
        return first_match and solve(i + 1, j + 1)
    return solve(0, 0)


def is_match_brute(s: str, p: str) -> bool:
    # Naive recursion (exponential) — same logic as memo but without cache; oracle for small inputs.
    def solve(i: int, j: int) -> bool:
        if j == len(p):
            return i == len(s)
        first_match = i < len(s) and _matches(s[i], p[j])
        if j + 1 < len(p) and p[j + 1] == "*":
            return solve(i, j + 2) or (first_match and solve(i + 1, j))
        return first_match and solve(i + 1, j + 1)
    return solve(0, 0)


def edge_cases() -> None:
    assert is_match_dp("aa", "a") is False
    assert is_match_dp("aa", "a*") is True
    assert is_match_dp("ab", ".*") is True
    assert is_match_dp("aab", "c*a*b") is True
    assert is_match_dp("mississippi", "mis*is*p*.") is False
    assert is_match_dp("", "") is True
    assert is_match_dp("", "a*") is True
    assert is_match_dp("", "a*b*c*") is True
    assert is_match_dp("a", "") is False
    assert is_match_dp("a", ".*..a*") is False
    print("edge_cases: PASS")


def _random_pattern(rng: random.Random, max_len: int, alphabet: str) -> str:
    out = []
    while len(out) < max_len:
        c = rng.choice(alphabet + ".")
        out.append(c)
        if rng.random() < 0.35:
            out.append("*")
    return "".join(out)


def stress_test() -> None:
    rng = random.Random(42)
    alphabet = "ab"
    for trial in range(300):
        s = "".join(rng.choice(alphabet) for _ in range(rng.randint(0, 5)))
        p = _random_pattern(rng, rng.randint(0, 5), alphabet)
        a = is_match_dp(s, p)
        b = is_match_memo(s, p)
        c = is_match_brute(s, p)
        assert a == b == c, f"trial {trial}: s={s!r} p={p!r} dp={a} memo={b} brute={c}"
    print("stress_test: 300 trials — iterative DP, memoized, brute recursion all agree.")


if __name__ == "__main__":
    edge_cases()
    stress_test()
    print("ALL TESTS PASSED")