Hard

Regular Expression Matching

LAB

Return true if pattern p fully matches s, where . matches one character and * repeats the previous token zero or more times.

EXAMPLES

Example 1

Input
{
  "s": "aa",
  "p": "a*"
}

Output
true

FUNCTION SHAPE

s: stringp: string→bool

SOLUTION NOTE

Handle '*' by either matching zero (skip pattern by 2) or matching one+ (if first matches, advance string but keep pattern).

Reveal reference solution +

pythonREFERENCE

def isMatch(self, s: str, p: str) -> bool:
    @cache
    def dp(i, j):
        if j >= len(p): return i >= len(s)

        first_match = i < len(s) and (p[j] == s[i] or p[j] == '.')

        if j + 1 < len(p) and p[j+1] == '*':
            # '*' matches zero OR one+ of preceding
            return dp(i, j+2) or (first_match and dp(i+1, j))
        else:
            return first_match and dp(i+1, j+1)

    return dp(0, 0)

TimeO(m × n)

SpaceO(m × n)

Open on LeetCode ↗