Problem statement

https://binarysearch.com/problems/Regular-Expression-Matching/

Solution

Almost the same as Leetcode 10. Regular Expression Matching, but we have one more case when we can have * in the beginning.

Complexity

It is O(m * n) for time and space.

Code

class Solution:
    def solve(self, p, s):
        m, n = len(s), len(p)
        @lru_cache(None)
        def dp(i, j):
            if j == -2: return False
            if j == - 1: return i == -1

            if p[j] == '*':
                return dp(i, j - 2) or (i >= 0 and p[j-1] in {s[i], "."} and dp(i - 1, j))
            if i >= 0: return p[j] in {s[i], "."} and dp(i - 1, j - 1)
            
            return False

        return dp(m - 1, n - 1)