Regular Expression Matching

Problem Implement regex matching over the FULL string s for patterns with '.' (any single char) and '*' (zero or more of the PRECEDING element).

Input / Output

• Input: string s, pattern p. Output: boolean full-match.

Constraints

• |s|, |p| <= 20–1000 depending on variant; O(|s|·|p|) DP expected; naive recursion is exponential.

Example

• s="aa", p="a*" → true; s="ab", p="." → true; s="aab", p="cab" → true (c matches empty); s="mississippi", p="misisp*." → false.

Expected approach

• DP: dp[i][j] = s[0..i) matches p[0..j). Transitions: p[j−1] normal/'.' → dp[i−1][j−1] on char match; p[j−1]=='' → dp[i][j−2] (zero copies) OR (dp[i−1][j] when s[i−1] matches p[j−2]) (one more copy). Base: dp[0][0]=true; dp[0][j] true for x chains. O(mn) time/space. The ''-binds-to-previous-element modeling and the empty-string row are where candidates fail. Memoized recursion is equivalent; contrast with LC44 wildcard matching ('' = any sequence) — different transition, frequent probe.