Regular expression matching

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        @cache
        def dp(i, j):
            if j == n:
                return i == m
            if i == m:
                if (n - j) % 2 == 1:
                    return False
                for k in range(j + 1, n, 2):
                    if p[k] != "*":
                        return False
                return True

            res = False

            if s[i] == p[j] or p[j] == '.':
                if j < n - 1 and p[j + 1] == '*':
                    res = dp(i, j + 2) or dp(i + 1, j)
                else:
                    res = dp(i + 1, j + 1)
            else:
                if j < n - 1 and p[j + 1] == "*":
                    res = dp(i, j + 2)
                else:
                    res = False
            return res

        return dp(0, 0)



        # i = 0
        # j = 0
        # while i < len(s) and j < len(p):
        #     print(i, j)
        #     if s[i] == p[j]:
        #         i += 1
        #         j += 1
        #     else:
        #         if p[j] == '.':
        #             i += 1
        #             j += 1
        #         elif p[j] == '*':
        #             if p[j - 1] == '.':
        #                 return True
        #             if s[i] == p[j - 1]:
        #                 i += 1
        #             else:
        #                 if s[i] == p[j + 1]:
        #                     i += 1
        #                     j += 1
        #                 else:
        #                     return False
        #         else:
        #             j += 1
        # return True if i == len(s) - 1 and j == len(p) - 1 else False

Regular Expression Matching

Difficulty: Hard

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 (.)".

 

Constraints:

  • 1 <= s.length <= 20
  • 1 <= p.length <= 20
  • s contains only lowercase English letters.
  • p contains only lowercase English letters, '.', and '*'.
  • It is guaranteed for each appearance of the character '*', there will be a previous valid character to match.