The Question
Coding

Regex Pattern Matcher

Design a system to determine if a given text string matches a specific formatting pattern. The pattern supports two special markers: a single-character wildcard that represents any individual character, and a repetition wildcard that allows the immediately preceding character to appear zero or more times. Your implementation must validate if the pattern matches the entire text string, not just a portion of it.
Java
Dynamic Programming
2D Array
Questions & Insights

Clarifying Questions

What are the maximum lengths for strings s and p? (Assuming s.length, p.length \leq 20 or 30 which suggests a O(N \cdot M) or O(2^{N+M}) approach).
Can the pattern p contain consecutive asterisks (e.g., a) or start with an asterisk? (Assuming p is always a valid regular expression where every is preceded by a valid character or .).
Are the strings restricted to lowercase English letters? (Assuming yes, plus the special characters . and ).
How should an empty string s and an empty pattern p be handled? (Assuming two empty strings match).
Assumptions:
s and p consist of lowercase English letters, ., and .
The pattern p will always be valid (no leading , no ).
The matching must be an exact match for the entire string s.

Thinking Process

Recursive Breakdown: The problem can be solved by comparing the first characters and then recursing. If the second character of the pattern is , the logic branches into two paths: either ignoring the char sequence (zero occurrences) or consuming one character of the string if it matches and staying at the current pattern state (one or more occurrences).
Base Case: If the pattern is empty, the string must also be empty for a match. If the string is empty but the pattern is not, the pattern could still match if it consists of sequences like a*b.
First Match Logic: A character s[i] matches p[j] if s[i] == p[j] or p[j] == '.'. This is a prerequisite for advancing the string index.
Dynamic Programming/Memoization: Since many sub-problems (pairs of indices i, j) are visited multiple times, we use a 2D array or a Map to store results of isMatch(i, j) to ensure O(N \cdot M) complexity.
Implementation Breakdown

Problem Set

Functional Requirement: Implement a function isMatch(String s, String p) that returns true if s matches p under regex rules.
Constraints:
Time Complexity: O(N \cdot M).
Space Complexity: O(N \cdot M) for the memoization table.
1 \leq s.length \leq 20.
1 \leq p.length \leq 20.

Approach

Algorithm: Dynamic Programming (Top-Down Memoization).
Data Structure: 2D Boolean array for memoization.
Complexity:
Time: O(S \cdot P) where S and P are lengths of the string and pattern respectively.
Space: O(S \cdot P) for the memoization table and recursion stack.

Implementation