Leetcode 10 Solution

Leetcode Question Link

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

Thinking Process

For this question, we are going to simulate the matching process of the regex. Let’s first assume M(i, j) means whether s[i:] can be matched by p[j:]. We can calculate M(i, j) recursively.

• If i == len(s) and j == len(p), we have a match.
• If i != len(s) and j == len(p), they don’t match.
• Otherwise, there are three rules to move forward:
  • If p[j + 1] is *, that means we can use p[j] to match any number of it in s, and then we can focus on a smaller scale problem, which M(i + k, j + 2), where k is the number of p[j] matched after s[i].
  • If p[j] is ., we go into M(i + 1, j + 1).
  • If s[i] == p[j], we go into M(i + 1, j + 1).
  • Otherwise, there is no match.

The result of the original question is M(0, 0).

Time & Space Complexity

Assuming M is the size of s, N is the size of p

• Time complexity: O(M^N) (because in the recursion, we go N layers, and for each layer, there are at most M branches)
• Space complexity: O(N)

Solution

class Solution:
    def isMatch(self, s: str, p: str) -> bool:

        @functools.cache
        def is_match(s, p, i, j):
            while j < len(p):
                if j + 1 < len(p) and p[j + 1] == '*':
                    for k in range(i, len(s)):
                        if is_match(s, p, k, j + 2):
                            return True

                        if not (p[j] == '.' or p[j] == s[k]):
                            break
                    else:
                        if is_match(s, p, len(s), j + 2):
                            return True
                    return False

                if i < len(s) and (p[j] == '.' or p[j] == s[i]):
                    i += 1
                    j += 1
                else:
                    break

            if j == len(p):
                return i == len(s)

            return False

        return is_match(s, p, 0, 0)