#44

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Wildcard Matching

Implement full wildcard pattern matching using '?' and '*' by applying state transition dynamic programming with careful handling of edge cases.

string dynamic programming greedy recursion

Problem Statement

You are given an input string s and a pattern p where p may include '?' and '' wildcards. '?' matches any single character, and ' ' matches any sequence of characters (including empty sequences). Your task is to implement a function that returns true if the pattern matches the entire input string and false otherwise. Partial matches are not allowed, and careful handling of consecutive '*' characters is required to avoid overcounting.

For example, given s = "aa" and p = "a", the output is false because the pattern does not cover all characters. If s = "aa" and p = "", the output is true because ' ' matches any sequence. Inputs may include up to 2000 characters, and only lowercase letters appear in s and p, making efficiency important for both time and space.

Examples

Example 1

Input: s = "aa", p = "a"

Output: false

"a" does not match the entire string "aa".

Example 2

Input: s = "aa", p = "*"

Output: true

'*' matches any sequence.

Example 3

Input: s = "cb", p = "?a"

Output: false

'?' matches 'c', but the second letter is 'a', which does not match 'b'.

Constraints

0 <= s.length, p.length <= 2000
s contains only lowercase English letters.
p contains only lowercase English letters, '?' or '*'.

Solution Approach

Dynamic Programming Table Construction

Build a 2D DP table dp[i][j] where dp[i][j] indicates whether the first i characters of s match the first j characters of p. Initialize dp[0][0] to true and fill the table row by row. Handle '?' as a match for a single character and '*' as matching zero or more characters by referencing previous rows. This approach ensures systematic exploration of all state transitions and avoids recursion overhead, maintaining correctness even with complex patterns.

Greedy Optimization with Two Pointers

Use two pointers, one for the string and one for the pattern, to iterate through both. Track the last '' encountered and attempt to match as many characters as possible, backtracking only when necessary. This greedy approach reduces unnecessary computations compared to full DP while preserving correctness. It directly addresses the common failure mode of misaligned ' ' expansion by explicitly recording previous match positions and adjusting pointers to recover from mismatches.

Recursive Memoization Strategy

Implement a recursive function that tries matching the string and pattern from the current indices, storing results in a memoization map to avoid repeated calculations. Handle '?' and '' according to their matching rules. This approach captures the natural recursive structure of state transitions and ensures that overlapping subproblems are computed only once, which mitigates exponential blowup while preserving the flexibility to handle edge cases like consecutive ' ' or empty strings.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the approach: full DP takes O(m n) with m = s.length and n = p.length, while greedy optimization can be closer to O(m+n) in practice. Space complexity varies similarly: the DP table requires O(m n) space, recursive memoization also may need O(m*n) for memo, and the greedy method can reduce space to O(1). These complexities reflect careful consideration of state transitions and wildcard handling.

What Interviewers Usually Probe

Do you correctly handle '*' matching multiple characters without skipping necessary DP states?
Can you optimize space usage while maintaining full string coverage matching?
Will you explain how consecutive '?' and '*' affect your state transitions and edge cases?

Common Pitfalls or Variants

Common pitfalls

Failing to initialize the DP table for empty strings or patterns with leading '*' characters.
Mismanaging backtracking when '*' is involved, causing incorrect false negatives.
Overlooking the need to match the entire string, allowing partial matches to incorrectly return true.

Follow-up variants

Matching with additional character classes like [a-z] or numeric ranges in the pattern.
Wildcard Matching II: pattern allows escape characters and nested wildcards requiring modified DP transitions.
Minimum edits required to transform string s to match pattern p considering '?' and '*' insertions.

FAQ

What is the main pattern used in Wildcard Matching?

Wildcard Matching primarily uses state transition dynamic programming to track all possible matches between the input string and pattern efficiently.

How does '*' affect matching in this problem?

The '*' character matches zero or more characters, requiring careful tracking of previous match positions to ensure correct backtracking and coverage.

Can '?' match multiple characters?

No, '?' matches exactly one character; the DP or greedy approach must account for single-character consumption and proper index advancement.

What are typical edge cases to test?

Edge cases include empty strings, patterns starting or ending with '', consecutive ' ' characters, and strings longer than the pattern to ensure full coverage matching.

Which approach is most efficient for large inputs?

The greedy two-pointer method often reduces time and space overhead compared to full DP while maintaining correctness, especially with long strings and patterns containing '*'.

terminal

Solution

Solution 1: Memoization Search

We design a function $dfs(i, j)$, which represents whether the string $s$ starting from the $i$-th character matches the string $p$ starting from the $j$-th character. The answer is $dfs(0, 0)$.

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        @cache
        def dfs(i: int, j: int) -> bool:
            if i >= len(s):
                return j >= len(p) or (p[j] == "*" and dfs(i, j + 1))
            if j >= len(p):
                return False
            if p[j] == "*":
                return dfs(i + 1, j) or dfs(i + 1, j + 1) or dfs(i, j + 1)
            return (p[j] == "?" or s[i] == p[j]) and dfs(i + 1, j + 1)

        return dfs(0, 0)

Solution 2: Dynamic Programming

We can convert the memoization search in Solution 1 into dynamic programming.

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        @cache
        def dfs(i: int, j: int) -> bool:
            if i >= len(s):
                return j >= len(p) or (p[j] == "*" and dfs(i, j + 1))
            if j >= len(p):
                return False
            if p[j] == "*":
                return dfs(i + 1, j) or dfs(i + 1, j + 1) or dfs(i, j + 1)
            return (p[j] == "?" or s[i] == p[j]) and dfs(i + 1, j + 1)

        return dfs(0, 0)

Continue Practicing

#241 different ways to add parentheses #678 valid parenthesis string #45 jump game ii