solution.py

"""
Code generated by https://github.com/goodstudyqaq/leetcode-local-tester
"""
try:
    from utils.python3.help import *
except ImportError:
    pass # In leetcode environment, we don't need to import the help file.

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        n = len(s)
        m = len(p)
        dp = [[False] * (m + 1) for _ in range(n + 1)] # dp[i][j] means s[i - 1:] matches p[j - 1:]
        
        @lru_cache()
        def dfs(l1, l2):
            if l1 == n + 1 and l2 == m + 1: # match successfully
                return True
            if l2 > m:
                return False # pattern is empty, but string is not empty

            # Why we don't check whether l1 > n? because if s is empty and p has '*', it is possible.

            # check whether p[l2] is '*'
            if l2 < m and p[l2] == '*':
                it = p[l2 - 1]
                # match zero
                if dfs(l1, l2 + 2):
                    return True
                # match one or more
                for i in range(l1 - 1, n):
                    if s[i] == it or it == '.':
                        if dfs(i + 2, l2 + 2):
                            return True
                    else:
                        break
                return False
            else:
                if l1 > n: # s is empty, but p is not
                    return False
                if s[l1 - 1] == p[l2 - 1] or p[l2 - 1] == '.':
                    return dfs(l1 + 1, l2 + 1)
                else:
                    return False
        return dfs(1, 1)