Regular expression matching with dot and star

Decide whether a whole string matches a pattern. The pattern has lowercase letters, . which matches any single character, and * which matches zero or more copies of the element right before it. The match must cover the entire string, not part of it.

Interface

Unless you agree on a different interface with the interviewer, assume:

• is_match(s: str, p: str) -> bool

Example

is_match("aa", "a")                   ->  False   # the pattern covers only one a
is_match("aa", "a*")                  ->  True
is_match("ab", ".*")                  ->  True
is_match("aab", "c*a*b")              ->  True    # c* matches zero c's
is_match("mississippi", "mis*is*p*.") ->  False
is_match("", "a*")                    ->  True

Constraints

• 0 <= len(s), len(p) <= 20 (be ready for larger).
• s has lowercase letters; p has lowercase letters, . and *. Every * follows a letter or ..

Clarifying questions

• Whole-string match or substring search?
• Can the pattern start with *, or have **?
• Does . match an empty string? (No, exactly one character.)

What a strong answer covers

• The recursion on (i, j): when p[j + 1] is *, either skip the starred pair or consume one matching character and stay on it.
• Memoization or a bottom-up table: O(len(s) · len(p)) time and space.
• The empty-string cases, including patterns like a*b*c* that match nothing.
• Tests where greedy matching fails, such as "aaa" against "a*a".

Follow-ups

• Add + (one or more) and ? (zero or one).
• Wildcard matching instead: ? for one character, * for any sequence.
• How a real regex engine avoids exponential time (Thompson NFA).