Hard

Wildcard Matching

LAB

Return true if pattern p fully matches s, where ? matches one character and * matches any sequence.

EXAMPLES

Example 1

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

Output
true

FUNCTION SHAPE

s: stringp: string→bool

SOLUTION NOTE

Similar to regex but simpler. '*' can match empty (move j) or consume one char (move i, keep j). '?' must match exactly one char.

Reveal reference solution +

pythonREFERENCE

def isMatch(self, s: str, p: str) -> bool:
    @cache
    def dp(i, j):
        if i == len(s) and j == len(p):
            return True
        if j == len(p):
            return False
        if i == len(s):
            return p[j] == '*' and dp(i, j + 1)

        if p[j] == '?' or s[i] == p[j]:
            return dp(i + 1, j + 1)
        elif p[j] == '*':
            # Match nothing (j+1) or match one char (i+1, keep *)
            return dp(i, j + 1) or dp(i + 1, j)
        return False

    return dp(0, 0)

TimeO(m × n)

SpaceO(m × n)

Open on LeetCode ↗