Wildcard Matching

Wildcard Matching

What is this problem about?

"Wildcard Matching" is a string comparison challenge where you are given an input string and a pattern. The pattern can contain special characters: ? which matches any single character, and * which matches any sequence of characters (including an empty sequence). Your goal is to determine if the pattern matches the entire input string.

Why is this asked in interviews?

This is a high-difficulty question asked by nearly every major tech company, including Apple, Microsoft, and Meta. It tests a candidate's ability to handle complex branching logic and state transitions. It is an excellent test of Dynamic Programming (DP) and Recursion with Memoization. Interviewers want to see if you can correctly identify the base cases and manage the "explosion" of possibilities that the * character introduces.

Algorithmic pattern used

The problem can be solved using Dynamic Programming. You create a 2D boolean table dp[i][j] representing whether the first i characters of the string match the first j characters of the pattern.

• If pattern[j] is ? or matches string[i], then dp[i][j] = dp[i-1][j-1].
• If pattern[j] is *, it can either match zero characters (dp[i][j-1]) or match one or more characters (dp[i-1][j]).

Example explanation

String: acdcb, Pattern: a*c?b.

1. a matches a.
2. * can match nothing, c, cd, or cdc.
3. If * matches cd, we look for c?b matching cb.
4. c matches c.
5. ? matches b.
6. Wait, the last b in the pattern doesn't have anything to match if ? took the b.
7. Actually, * matches cd, then c matches c, ? matches b? No, the string is acdcb. Let's re-evaluate:
   • a matches a.
   • * matches d.
   • c matches c.
   • ? matches b? No, the string is acdcb.
   • Correct match: a -> a, * -> cd, c -> c, ? -> b. String length is 5, pattern components cover all. Total match!

Common mistakes candidates make

• Inefficient Recursion: Not using memoization, leading to exponential time complexity O(2^N) when multiple * are present.
• Base Case for *: Forgetting that * can match an empty string at the beginning of the pattern.
• Greedy Trap: Trying to use a simple greedy approach for * without backtracking or DP, which fails on cases like s="aaab", p="*ab".

Interview preparation tip

Practice the 2D DP table approach. Visualizing the transitions on a grid helps you understand how the * character "spreads" the truth values across the row and column.