Regular Expression Matching

Problem Statement

You are given an input string s consisting of lowercase English letters, and a pattern p consisting of lowercase English letters, as well as '.', and '*' characters.

Return true if the pattern matches the entire input string, otherwise return false.

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

Example 1:

Input: s = "aa", p = ".b"

Output: false

Explanation: Regardless of which character we choose for the '.' in the pattern, we cannot match the second character in the input string.

Example 2:

Input: s = "nnn", p = "n*"

Output: true

Explanation: '*' means zero or more of the preceding element, 'n'. We choose 'n' to repeat three times.

Example 3:

Input: s = "xyz", p = ".*z"

Output: true

Explanation: The pattern ".*" means zero or more of any character, so we choose ".." to match "xy" and "z" to match "z".

Constraints:

• 1 <= s.length <= 20
• 1 <= p.length <= 20
• Each appearance of '*', will be preceded by a valid character or '.'.

Recommended Time and Space Complexity

You should aim for a solution with O(m \cdot n) time and O(n) space, where m is the length of the string s and n is the length of the pattern p.

Solution

Recursion

def is_match(s: str, p: str) -> bool:
    m, n = len(s), len(p)

    def dfs(i, j):
        if j == n:
            return i == m

        match = i < m and (s[i] == p[j] or p[j] == ".")
        if (j + 1) < n and p[j + 1] == "*":
            return (dfs(i, j + 2) or          # don't use *
                   (match and dfs(i + 1, j))) # use *
        if match:
            return dfs(i + 1, j + 1)
        return False

    return dfs(0, 0)

Time complexity: O(2 ^ {m + n}) Space complexity: O(m + n)