# 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:

| Character | Meaning |
|---|---|
| `?` | Matches any single character |
| `*` | Matches any sequence of characters, including the empty sequence |

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

For example:

```python
s = "aa"
p = "a"
```

This returns:

```python
False
```

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

Another example:

```python
s = "aa"
p = "*"
```

This returns:

```python
True
```

The `*` can match the whole string `"aa"`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A string `s` and a pattern `p` |
| Output | `True` if the whole string matches the whole pattern |
| `?` | Matches exactly one character |
| `*` | Matches zero or more characters |

Function shape:

```python
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:

| Choice | Meaning |
|---|---|
| Match empty | `*` consumes no character from `s` |
| Match one or more | `*` consumes a character from `s` and may consume more |

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:

```python
dp[i][j]
```

mean:

```python
s[:i] matches p[:j]
```

So:

| State | Meaning |
|---|---|
| `dp[0][0]` | Empty string matches empty pattern |
| `dp[i][j]` | First `i` characters of `s` match first `j` characters of `p` |
| Answer | `dp[len(s)][len(p)]` |

This prefix definition makes empty strings easy to handle.

## DP Transitions

Let the current string character be:

```python
s[i - 1]
```

and the current pattern character be:

```python
p[j - 1]
```

There are three cases.

### Case 1: Same character

If:

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

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

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

### Case 2: Pattern has `?`

If:

```python
p[j - 1] == "?"
```

then `?` matches exactly one character.

So again:

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

### Case 3: Pattern has `*`

If:

```python
p[j - 1] == "*"
```

then `*` has two useful choices.

It can match empty:

```python
dp[i][j - 1]
```

Or it can match one more character from `s`:

```python
dp[i - 1][j]
```

So:

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

## Initialization

The empty string matches the empty pattern:

```python
dp[0][0] = True
```

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

For example:

```python
p = "***"
```

can match the empty string.

So we initialize the first row:

```python
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:

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

Create:

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

Set:

```python
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:

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

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

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

Return:

```python
dp[m][n]
```

## Walkthrough

Use:

```python
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:

```python
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(m * n)` | We fill one DP cell for each pair of string and pattern prefixes |
| Space | `O(m * n)` | The DP table has `(m + 1) * (n + 1)` cells |

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

## Implementation

```python
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:

```python
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:

```python
dp[0][0] = True
```

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

```python
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:

```python
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 `?`:

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

This is valid only when the current characters are compatible.

Finally:

```python
return dp[m][n]
```

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

## Testing

```python
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()
```

| Test | Expected | Reason |
|---|---:|---|
| `"aa"`, `"a"` | `False` | Match must cover the whole string |
| `"aa"`, `"*"` | `True` | `*` can match all characters |
| `"cb"`, `"?a"` | `False` | Last character does not match |
| `"adceb"`, `"*a*b"` | `True` | Stars can match flexible middle parts |
| `"acdcb"`, `"a*c?b"` | `False` | No star assignment makes the suffix match |
| `""`, `"*"` | `True` | `*` can match empty |
| `""`, `"?"` | `False` | `?` needs one character |