Leetcode 10 Solution

This article provides solution to leetcode question 10 (regular-expression-matching)

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)