LeetCode 44: Wildcard Matching

Problem Restatement

We are given an input string s and a pattern p.

The pattern may contain two special wildcard characters:

The match must cover the entire input string, not just part of it. The official problem states these wildcard rules directly.

For example:

s = "aa"
p = "a"

This returns:

False

The pattern "a" does not match the whole string "aa".

Another example:

s = "aa"
p = "*"

This returns:

True

The * can match the whole string "aa".

Input and Output

Function shape:

def isMatch(s: str, p: str) -> bool:
    ...

First Thought: Recursion

A natural way to think about this problem is to compare s and p from left to right.

If the current pattern character is a normal character, it must equal the current string character.

If the current pattern character is ?, it can match one character.

If the current pattern character is *, we have choices:

This branching suggests recursion.

But plain recursion repeats many states. For example, the same suffix of s and the same suffix of p can be reached in different ways. We need dynamic programming to avoid repeated work.

Key Insight

Define a DP state using prefixes.

Let:

dp[i][j]

mean:

s[:i] matches p[:j]

So:

This prefix definition makes empty strings easy to handle.

DP Transitions

Let the current string character be:

s[i - 1]

and the current pattern character be:

p[j - 1]

There are three cases.

Case 1: Same character

If:

s[i - 1] == p[j - 1]

then the current characters match, so we rely on the previous prefixes:

dp[i][j] = dp[i - 1][j - 1]

Case 2: Pattern has ?

If:

p[j - 1] == "?"

then ? matches exactly one character.

So again:

dp[i][j] = dp[i - 1][j - 1]

Case 3: Pattern has *

If:

p[j - 1] == "*"

then * has two useful choices.

It can match empty:

dp[i][j - 1]

Or it can match one more character from s:

dp[i - 1][j]

So:

dp[i][j] = dp[i][j - 1] or dp[i - 1][j]

Initialization

The empty string matches the empty pattern:

dp[0][0] = True

For an empty string s, only patterns made entirely of * can match it.

For example:

p = "***"

can match the empty string.

So we initialize the first row:

for j in range(1, n + 1):
    if p[j - 1] == "*":
        dp[0][j] = dp[0][j - 1]

If a non-star appears, the rest cannot match the empty string unless earlier state is already false.

Algorithm

Let:

m = len(s)
n = len(p)

Create:

dp = [[False] * (n + 1) for _ in range(m + 1)]

Set:

dp[0][0] = True

Initialize matches between the empty string and star-only pattern prefixes.

Then fill the table row by row.

For each i from 1 to m and each j from 1 to n:

If p[j - 1] == "*", use:

dp[i][j] = dp[i][j - 1] or dp[i - 1][j]

Otherwise, if the current characters match or the pattern has ?, use:

dp[i][j] = dp[i - 1][j - 1]

Return:

dp[m][n]

Walkthrough

Use:

s = "adceb"
p = "*a*b"

The answer is True.

The first * can match the empty sequence.

Then a matches a.

The second * can match "dce".

Finally, b matches b.

So the whole string is matched by the whole pattern.

Now consider:

s = "acdcb"
p = "a*c?b"

The answer is False.

The pattern starts with a, which matches.

The * can consume some middle characters.

But the remaining part c?b must match the end of the string in order. No choice for * makes the full pattern match the full string.

Correctness

We prove that dp[i][j] is true exactly when s[:i] matches p[:j].

The base case is dp[0][0] = True, because two empty prefixes match.

For the first row, dp[0][j] is true only when p[:j] can match the empty string. This is possible only if every character in that pattern prefix is *, because ? and normal characters require one character from s.

For the transition, suppose p[j - 1] is a normal character. Then it can only match if it equals s[i - 1], and the earlier prefixes must also match. This is exactly dp[i - 1][j - 1].

If p[j - 1] is ?, it matches exactly one character, so the earlier prefixes must match. This is also dp[i - 1][j - 1].

If p[j - 1] is *, there are two complete possibilities. It either matches no character, leaving the match to dp[i][j - 1], or it matches at least one character, leaving the same * available to match more characters, represented by dp[i - 1][j].

These cases cover all legal wildcard behavior. Therefore each DP entry is computed correctly, and dp[m][n] gives whether the full string matches the full pattern.

Complexity

Here, m = len(s) and n = len(p).

Implementation

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m = len(s)
        n = len(p)

        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[0][0] = True

        for j in range(1, n + 1):
            if p[j - 1] == "*":
                dp[0][j] = dp[0][j - 1]

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if p[j - 1] == "*":
                    dp[i][j] = dp[i][j - 1] or dp[i - 1][j]
                elif p[j - 1] == "?" or p[j - 1] == s[i - 1]:
                    dp[i][j] = dp[i - 1][j - 1]

        return dp[m][n]

Code Explanation

We create a DP table with one extra row and one extra column:

dp = [[False] * (n + 1) for _ in range(m + 1)]

The extra row represents the empty prefix of s.

The extra column represents the empty prefix of p.

The empty string matches the empty pattern:

dp[0][0] = True

Then we initialize pattern prefixes that can match the empty string:

for j in range(1, n + 1):
    if p[j - 1] == "*":
        dp[0][j] = dp[0][j - 1]

Then we fill the rest of the table.

For a star:

dp[i][j] = dp[i][j - 1] or dp[i - 1][j]

dp[i][j - 1] means the star matches empty.

dp[i - 1][j] means the star consumes one more character.

For a normal character or ?:

dp[i][j] = dp[i - 1][j - 1]

This is valid only when the current characters are compatible.

Finally:

return dp[m][n]

This tells us whether the whole string matches the whole pattern.

Testing

def run_tests():
    s = Solution()

    assert s.isMatch("aa", "a") is False
    assert s.isMatch("aa", "*") is True
    assert s.isMatch("cb", "?a") is False
    assert s.isMatch("adceb", "*a*b") is True
    assert s.isMatch("acdcb", "a*c?b") is False
    assert s.isMatch("", "*") is True
    assert s.isMatch("", "?") is False
    assert s.isMatch("abc", "abc") is True
    assert s.isMatch("abc", "a*") is True
    assert s.isMatch("abc", "*?c") is True

    print("all tests passed")

run_tests()