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.