Regular Expression Matching

Problem

Implement a matcher that decides whether a string s is matched entirely by a pattern p. The pattern may contain lowercase letters, . which matches any single character, and * which means "zero or more repetitions of the element immediately before it". A * is never the first character of p, and the match must cover all of s, not just a prefix.

• Both the text and the pattern are up to 25 characters long.
• s contains only lowercase letters; p contains lowercase letters, ., and *.

Examples

• s = "bb", p = "b" → false. The pattern consumes one b and stops.
• s = "bb", p = "b*" → true. b* expands to two b's.
• s = "cd", p = ".*" → true. .* means any character repeated, so it absorbs everything.
• s = "ccd", p = "x*c*d" → true. x* matches nothing, c* matches cc, d matches d.

Hints

1. Try to match from the left one unit at a time, where a unit is either a single pattern character or a character followed by *.
2. When the next unit is x*, you have exactly two choices: use it zero times and skip it, or consume one matching character of s and keep the same x* in play.
3. Memoise on (i, j) positions, or fill a bottom-up table dp[i][j] = does s[i:] match p[j:].