Wildcard Matching - Video Solutions

Problem Overview: Wildcard Matching checks whether an entire string s matches a pattern p that may contain two special characters: ? (matches any single character) and * (matches any sequence of characters, including empty). The goal is to return true if the whole string can be matched by the pattern, otherwise false.

Approach 1: Dynamic Programming (O(m*n) time, O(m*n) space)

This approach models the problem as a state transition using dynamic programming. Create a 2D table dp[i][j] where each state represents whether the first i characters of s match the first j characters of p. If characters match or the pattern has ?, the result depends on the previous diagonal state dp[i-1][j-1]. When encountering *, two possibilities exist: treat it as matching zero characters (dp[i][j-1]) or match one more character from the string (dp[i-1][j]). Initialization is critical because leading * characters can match an empty string. This solution systematically evaluates all subproblems and guarantees correctness for every edge case.

DP is reliable for interview discussion because it clearly expresses the recursive relationship between pattern and string prefixes. The tradeoff is memory usage: storing a full table requires O(m*n) space, though it can be optimized to O(n) by keeping only the previous row.

Approach 2: Greedy Two-Pointer Algorithm (O(m+n) time, O(1) space)

A faster solution uses a greedy strategy with two pointers scanning the string and pattern. Track four values: the current index in s, the current index in p, the most recent * position in the pattern, and the position in the string where that star started matching. When characters match or the pattern has ?, advance both pointers. When encountering *, record its position and attempt to match zero characters first. If a mismatch occurs later, backtrack to the last * and expand its match by one additional character in the string.

This works because * can represent any substring length, so the algorithm greedily tries minimal matches and only expands when needed. The scan never moves backward in the pattern except to the stored star position, which keeps the runtime linear. The method relies heavily on careful pointer management and is commonly categorized under string processing techniques.

Recommended for interviews: Interviewers often expect the Dynamic Programming reasoning first because it demonstrates understanding of overlapping subproblems and pattern matching logic. After that, presenting the Greedy two-pointer optimization shows deeper algorithmic insight since it reduces complexity to O(m+n) time and O(1) space. Showing both approaches signals strong problem-solving depth.