← Create New Paste

Wildcard Matching (LeetCode 44): From DP Table to Greedy Backtracking

11 views
Given a string s and a pattern p, return true if p matches all of s. The pattern may contain '?', which matches any single character, and '*', which matches any sequence of characters, including the empty sequence. It is a hard-tagged problem, but it becomes manageable once you see the two standard solutions and can explain why both work. Start by restating the rules Before writing code, say the rules back: matching must cover the entire string, '?' consumes exactly one character, and '*' can consume zero or more. Then mention the edge cases you will test: empty string with pattern "*" (true), empty string with pattern "?" (false), and patterns with several stars in a row, which behave like a single star. Solution 1: dynamic programming Let dp[i][j] mean "the first i characters of s are matched by the first j characters of p." - dp[0][0] = True. - dp[0][j] is True only if p[0..j-1] is all stars. - If p[j-1] is a letter or '?': dp[i][j] = dp[i-1][j-1] and (p[j-1] == '?' or p[j-1] == s[i-1]). - If p[j-1] is '*': dp[i][j] = dp[i][j-1] (star matches nothing) or dp[i-1][j] (star absorbs one more character of s). def isMatch(s, p): m, n = len(s), len(p) dp = [[False] * (n + 1) for _ in range(m + 1)] dp[0][0] = True for j in range(1, n + 1): dp[0][j] = dp[0][j - 1] and p[j - 1] == '*' for i in range(1, m + 1): for j in range(1, n + 1): if p[j - 1] == '*': dp[i][j] = dp[i][j - 1] or dp[i - 1][j] elif p[j - 1] == '?' or p[j - 1] == s[i - 1]: dp[i][j] = dp[i - 1][j - 1] return dp[m][n] Time and space are O(m*n). Point out that each row only depends on the previous one, so space can drop to O(n). The star transition is the part interviewers probe. Explain it as a choice: either the star is finished (move left in the pattern) or it eats the current character and stays available (move up in the string). Solution 2: greedy with backtracking to the last star There is a faster practical approach. Walk both strings with pointers i and j. On a direct match or '?', advance both. On '*', remember its position (star = j) and the string position at that moment (mark = i), then advance j, initially letting the star match nothing. On a mismatch, if a star was seen, backtrack: let the star absorb one more character (mark += 1, i = mark, j = star + 1). If no star was seen, return False. At the end, skip any trailing stars and check that the pattern is exhausted. Why is it safe to remember only the last star? Because a later star can absorb anything an earlier star would have needed to absorb, so expanding the most recent star is never worse. Saying this out loud is what separates a memorized answer from an understood one. Worst-case time is O(m*n), but typical inputs run close to linear with O(1) extra space. Common bugs - Forgetting to initialize dp[0][j] for leading stars. - Confusing this problem with Regular Expression Matching (LeetCode 10), where '*' modifies the previous character. Mention the difference if the interviewer asks a follow-up. - In the greedy version, not consuming trailing stars after the loop. Talking through a hard problem live The difficulty with problems like this is staying organized while explaining transitions under pressure. Linkjob AI (https://linkjob.ai) gives real-time help during live job interviews and technical interviews, which can help you keep the structure clear when the interviewer starts asking "why does that transition hold?"
Created Nov 18, 2026 01:31 Expires Nov 18, 2027 01:31