Wildcard Matching
Given an input string $s$ and a pattern $p$, implement wildcard matching with support for '?' (matches any single character) and '*' (matches any sequence). Use DP.
Why Interviewers Ask This
Adobe asks this to evaluate a candidate's mastery of dynamic programming and recursive thinking under pressure. The problem tests the ability to handle state transitions with multiple wildcard rules, specifically managing the non-deterministic nature of the asterisk character. It reveals whether you can optimize naive recursion into an efficient solution while maintaining code clarity.
How to Answer This Question
1. Clarify edge cases immediately, such as empty strings or patterns containing only asterisks, which Adobe often uses to test robustness. 2. Propose a brute-force recursive solution first to establish a baseline understanding of the matching logic for '?' and '*'. 3. Identify overlapping subproblems in the recursion tree to justify the need for Dynamic Programming. 4. Define the DP state explicitly, typically a 2D boolean array where dp[i][j] represents if s[0...i-1] matches p[0...j-1]. 5. Derive the recurrence relation carefully: handle '*' by considering both skipping it and using it to match one or more characters. 6. Optimize space complexity if possible, but prioritize correctness first. 7. Walk through a concrete example like 'aa' and 'a*' to validate your logic before coding.
Key Points to Cover
- Explicitly defining the DP state transition for the '*' wildcard
- Correctly initializing the first row to handle leading asterisks
- Demonstrating understanding of why recursion leads to exponential time without memoization
- Handling edge cases like empty input strings gracefully
- Articulating the difference between greedy approaches and DP for this specific problem
Sample Answer
To solve this Wildcard Matching problem efficiently, I would start by analyzing the constraints. Since we have two variable-length inputs, a brute-force approach checking every combination is too slow. Instead, I will use Dynamic Programming to build a table that stores intermediate results.
First, I define a 2D boolean array dp with dimensions (s.length + 1) x (p.length + 1). The base case is dp[0][0], which is true because two empty strings match. If the pattern starts with asterisks, those are also valid matches against an empty string, so I initialize the first row accordingly.
Next, I iterate through each character of the string and pattern. For a normal character or '?', the current state depends on the previous diagonal value: dp[i][j] = dp[i-1][j-1] AND (s[i-1] == p[j-1] OR p[j-1] == '?').
The critical part is handling the '*'. If p[j-1] is '*', it can either match nothing, meaning we take the value from the left cell dp[i][j-1], or it can match one or more characters from the string, taking the value from the cell above dp[i-1][j]. So, dp[i][j] becomes true if either of these conditions is met. Finally, the answer is found at dp[s.length][p.length]. This approach ensures O(m*n) time complexity and handles all edge cases cleanly.
Common Mistakes to Avoid
- Attempting a greedy solution that fails when a '*' could match zero characters versus many
- Forgetting to initialize the DP table correctly for patterns starting with asterisks
- Confusing the '*' behavior with regex quantifiers like '+' or '{n}' without clarifying flexibility
- Overlooking the space optimization opportunity or failing to explain the O(m*n) complexity clearly
Practice This Question with AI
Answer this question orally or via text and get instant AI-powered feedback on your response quality, structure, and delivery.