217. Wildcard Pattern Matching

Given a text string and a pattern containing lowercase letters, '?' (matches exactly one character), and '*' (matches any sequence of characters, including an empty one), print 'Yes' if the pattern matches the entire text, otherwise 'No'.

Input: Two lines: the first contains the text string, the second contains the pattern string (either may be empty, since 0 is an allowed length). Output: Print "Yes" if the pattern matches the entire text, otherwise print "No".

0 <= |text|, |pattern| <= 1000

The base case handling for an EMPTY text or EMPTY pattern needs special care - a pattern of all '*' characters can match an empty text (dp[0][j] stays true as long as every earlier pattern character was also '*'), a common edge case to overlook.

Check whether a pattern (with '?' and '*' wildcards) matches an entire text string. Brute force: Try every possible way of expanding each '*' into a specific number of matched characters directly - this branches combinatorially for multiple '*' characters, when a single DP table handles all expansions implicitly. Optimised: The DP table captures BOTH interpretations of a '*' (matching zero characters, or matching one more character while still being 'active' for future characters) within a single recurrence - this avoids ever needing to explicitly try different expansion LENGTHS for each '*', since the table implicitly explores all of them via its two OR'd conditions.

Use the same recursive case analysis as brute force, but cache the result of every (text index, pattern index) pair the first time it is computed, so any later recursive call that lands on the same pair returns instantly instead of re-exploring the whole remaining match. Since there are only O(n*m) distinct pairs, memoization collapses the exponential tree of repeated subproblems down to a polynomial number of unique computations, which is the same idea underlying dynamic programming. Time: O(n*m) Space: O(n*m)

Recursively try to match pattern against text character by character: a literal or '?' must match the current text character exactly (advance both), and a '*' branches into either matching zero characters (skip the '*') or matching one more character of text and staying on the same '*' to potentially consume more. This directly encodes the definition of wildcard matching, but because '*' creates two recursive branches at every position, the same (text position, pattern position) pair gets recomputed many times over, causing exponential blowup. Time: O(2^(n+m)) Space: O(n+m)

Walk through text and pattern with two pointers, matching literals and '?' directly; whenever a '*' is encountered, remember its position and the current text position as a backtrack checkpoint, and greedily assume it matches zero characters. If a later mismatch occurs, fall back to the last remembered '*' checkpoint, let it consume one more text character than before, and resume from there. This achieves the same worst-case time as the DP table but replaces the full O(n*m) table with just a couple of index variables, since only the most recent '*' checkpoint ever needs to be remembered. Time: O(n*m) Space: O(1)

1. dp[i][j] = does pattern[0..j) match text[0..i)? 2. A '*' at pattern[j-1] means dp[i][j] is true if dp[i][j-1] is true (using ZERO characters of text for this '*') OR dp[i-1][j] is true (using ONE MORE character of text for this same '*'). 3. A '?' or matching literal character means dp[i][j] = dp[i-1][j-1]; a non-matching literal means dp[i][j] = false.

Time: O(|text| * |pattern|) - filling the DP table, one cell per pair of positions. Space: O(|text| * |pattern|) for the full table (reducible to O(|pattern|) with a rolling 1D array).

Test an empty text and/or empty pattern (0 <= length is explicitly allowed), a pattern of only '*' characters (matches any text), and both strings at length 1000 for the O(n*m) DP's performance.

Be ready to explain the '*' transition precisely (matching zero OR one-more characters) - this is the single trickiest part of the recurrence, and clearly justifying it (a '*' can 'give up' its greediness and stop matching at any point) shows real understanding.