How to Solve Wildcard Matching

This problem requires matching an entire input string against a pattern containing '?' and '' wildcards. Using state transition dynamic programming captures all matching possibilities while avoiding redundant recursion. Correct handling of '' expansion and '?' single-character matches is crucial for both correctness and performance in this problem.

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

The time complexity depends on the approach: full DP takes O(mn) 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(mn) 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.

How GhostInterview Helps

• Capture screenshots of string and pattern inputs, highlighting current characters and positions for live debugging.
• Provide step-by-step solution paths including DP table construction, greedy pointer tracking, and memoization explanations, with complexity annotations.
• Support interactive screen-share workflows where DP layers or pointer states are overlaid on input visualization, allowing detailed inspection of wildcard matches.

Topic Pages

• String
• Dynamic Programming
• Greedy
• Recursion

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

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 '*'.