Solution: Regular Expression Matching

Statement

You are given an input string, s, and a pattern string, p. Your task is to implement regular expression matching between s and p, where the pattern may include the special characters '.' and '*':

• '.' matches any single character.

• '*' matches zero or more occurrences of the preceding character.

The match must cover the entire input string, not just part of it.

Constraints:

• $1 \leq$ s.length $\leq 20$

• $1 \leq$ p.length $\leq 20$

• s contains only lowercase English letters.

• p contains only lowercase English letters, '.', and '*'.

• It is guaranteed that for each appearance of the character '*', there will be a previous valid character to match.

Solution

One of the first ideas that comes to mind to solve the regular expression matching problem is to compare the string s and the pattern p character by character. At each step, we could check if the current characters match, and when we encounter special symbols like '.' or '*', we could try to handle them separately. However, this naive approach quickly becomes complicated because the '*' operator can represent zero or more repetitions of the previous character, leading ...