Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where:

  • '.' Matches any single character.​​​​
  • '*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).


Example 1:

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Example 2:
Input: s = "aa", p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Example 3:

Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

A regular expression is a pattern that can be used to match strings. In this problem, we are given a regular expression pattern and a string, and we need to determine if the string matches the pattern. The pattern may contain two special characters: a dot '.' and a star '*'. The dot matches any single character, and the star matches zero or more occurrences of the preceding character.

To solve this problem, we can use a recursive approach. We start by checking if the pattern is empty. If it is, then the string must also be empty for the pattern to match the string. If the pattern is not empty, we check the first character of the pattern against the first character of the string. If they match (or if the first character of the pattern is a dot), we can continue to check the remaining characters of the string and pattern recursively. If the second character of the pattern is a star, we can also try matching the rest of the pattern against the string without consuming any characters.

Here is an implementation of this approach in Python:

Here is an implementation of this approach in Python:

def is_match(s: str, p: str) -> bool:
    if not p:
        return not s

    first_match = bool(s) and p[0] in {s[0], '.'}

    if len(p) >= 2 and p[1] == '*':
        return is_match(s, p[2:]) or (first_match and is_match(s[1:], p))
    else:
        return first_match and is_match(s[1:], p[1:])

This function uses recursion to check if the given string s matches the given pattern p. It checks the first character of the pattern against the first character of the string, and if they match (or if the first character of the pattern is a dot), it checks the remainder of the string and pattern recursively. If the second character of the pattern is a '*', then the function also tries matching the rest of the pattern against the string without consuming any characters.

Here is an example of using this function:

# "aa" does not match "a"
is_match("aa", "a")  # returns False

# "a" matches "a"
is_match("a", "a")  # returns True

# "a" matches "."
is_match("a", ".")  # returns True

# "a" matches "a*"
is_match("a", "a*")  # returns True

# "a" matches ".*"
is_match("a", ".*")  # returns True

# "ab" matches ".*"
is_match("ab", ".*")  # returns True


Note that this function is not very efficient, as it may take a long time to match longer strings or patterns. A more efficient implementation would use dynamic programming to avoid repeating the same computations multiple times. For example, we could use a two-dimensional array to store the results of previous computations and avoid repeating the same computation multiple times. This would significantly improve the performance of the algorithm for longer strings and patterns.