Problem statement

https://leetcode.com/problems/regular-expression-matching/

Solution

First approach is to use bruteforce with recursion, which have exponential time. We can also use DP approach, if we keep $0-1$ values match(text[:i], pattern[:j]) in our table.

  1. if p[j] == '*':
    1. dp(i, j) = True if dp(i, j - 2), for example s = ba, p = baq*
    2. dp(i, j) = True if i >= 0 and p[j-1] in {s[i], "."} and dp(i - 1, j), for example s = ba, p = ba* or b.*
  2. dp(i, j) = True if i >= 0 and p[j] in {s[i], "."} and dp(i - 1, j - 1), for example s = bac, p = bac or ba.

Complexity

Time and space complexity is $O(mn)$.

Code

class Solution:
    def isMatch(self, s, p):
        m, n = len(s), len(p)

        @lru_cache(None)
        def dp(i, j):
            if j == - 1: return i == -1

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

        return dp(m - 1, n - 1)