Regular Expression Matching

hard ~40 min

Write is_match(s: str, p: str) -> bool for a tiny regex language. The pattern must match all of s, not just part of it.

a letter matches that same letter,
. matches any single character,
x* (a letter or . followed by *) matches zero or more copies of x.

Examples:

is_match("aab", "c*a*b") == True (c* matches nothing, a* matches aa)
is_match("mississippi", "mis*is*p*.") == False
is_match("abc", ".*") == True
is_match("ab", "a") == False (must match the whole string)

Constraints: s has 0 to 30 lowercase letters; p has 0 to 30 characters from lowercase letters, . and *, and every * directly follows a letter or ..

Plain backtracking is exponential on patterns like a*a*a*...b, and one test uses exactly that; aim for O(len(s) · len(p)).

Show hint

the backtracking keeps asking the same question: does the rest of s from position i match the rest of p from position j? Answer each such question only once.

Topic: String DP (edit distance, LCS). dp[i][j] over prefixes of two strings; palindromes by expanding or by length.

Read the visual guide