Wildcard Matching LeetCode 44 — DP Guide

LeetCode 44 Wildcard Matching gives you an input string s and a pattern p. The pattern may contain two special characters: '?' matches exactly one arbitrary character, and '*' matches any sequence of characters including the empty sequence. Your task is to determine whether the pattern p matches the entire string s — not just a prefix or suffix, but the whole string from start to finish.

Unlike substring search or prefix matching, the entire string must be consumed by the pattern. A pattern like "a*b" must match strings starting with 'a' and ending with 'b', with '*' absorbing whatever lies between. A pattern like "?*?" requires at least two characters (one for each '?') with '*' optionally absorbing any middle characters. This full-match requirement is what drives the DP formulation.

The problem is closely related to LeetCode 10 Regular Expression Matching, but the wildcard semantics for '*' differ in a critical way. Understanding the distinction is the first conceptual step before writing any code.

In LeetCode 10 Regular Expression Matching, '*' is a quantifier that modifies the preceding character — "a*" means "zero or more 'a' characters" and ".*" means "zero or more of any character." The '*' cannot appear without a preceding character. In LeetCode 44 Wildcard Matching, '*' is a standalone operator with no dependency on what precedes it — it simply matches any sequence of zero or more characters on its own.

This distinction makes wildcard matching conceptually simpler. In regex matching, you must always consider the '*' together with the character before it, which complicates the DP transitions. In wildcard matching, when you encounter '*' in the pattern, there is exactly one choice: either '*' matches zero characters (skip the star in the pattern) or '*' matches one more character from s (advance s by one and keep the star). No lookahead at the preceding pattern character is needed.

Despite being simpler, wildcard matching still has the same worst-case complexity and the same general 2D DP structure as regex matching. Both use a dp[i][j] table where i indexes into s and j indexes into p. The recurrence transitions differ only at the '*' case, and the first-row initialization differs meaningfully: in wildcard DP, dp[0][j] is true as long as all pattern characters up to j are '*', since consecutive stars can all match the empty string.

The recursive solution starts from indices i=0 (position in s) and j=0 (position in p) and tries to match the entire string by consuming characters one at a time. When p[j] is a letter or '?', we check if s[i] matches (letter must be equal, '?' always matches any letter), then recurse on (i+1, j+1). If s[i] and p[j] do not match and p[j] is a letter, return false immediately.

When p[j] is '*', we have two branches: either '*' matches zero characters (recurse on (i, j+1), advancing only in the pattern), or '*' matches one more character from s (recurse on (i+1, j), advancing s but keeping the star active for potentially more characters). The recursion returns true if either branch returns true. The base cases are: if both i and j reach the ends of their strings simultaneously, return true; if j reaches the end of p but i has not reached the end of s, return false; if i reaches the end of s but j has not reached the end of p, return true only if all remaining pattern characters are '*'.

Without memoization this recursion has exponential time due to overlapping subproblems — the same (i, j) pair is evaluated repeatedly when multiple '*' operators are in the pattern. Memoizing on the pair (i, j) reduces the time to O(m·n) where m = len(s) and n = len(p), with O(m·n) additional space for the memo table. The bottom-up DP approach eliminates the recursion overhead and makes the initialization structure explicit.

Define dp[i][j] as true if s[0..i-1] (the first i characters of s) fully matches p[0..j-1] (the first j characters of p). The table is (m+1) × (n+1) where m = len(s) and n = len(p). The answer is dp[m][n]. The base case dp[0][0] = true means an empty string matches an empty pattern.

The recurrence has three cases. (1) If p[j-1] is a letter: dp[i][j] = dp[i-1][j-1] AND s[i-1] == p[j-1]. (2) If p[j-1] == '?': dp[i][j] = dp[i-1][j-1], since '?' matches any single character — i must be at least 1. (3) If p[j-1] == '*': dp[i][j] = dp[i][j-1] OR dp[i-1][j]. The first option dp[i][j-1] means '*' matches the empty sequence (ignore the star, advance j). The second option dp[i-1][j] means '*' matches one more character from s (advance i, keep j pointing at the star).

The '*' transition dp[i][j] = dp[i][j-1] OR dp[i-1][j] is the heart of the algorithm. By keeping j fixed when advancing i (dp[i-1][j]), the '*' can absorb arbitrarily many characters through repeated application — each time we look at dp[i-1][j], that cell itself was filled using the same '*' transition at position (i-1, j), allowing a chain that consumes any number of characters from s.

The first row dp[0][j] answers: does the first j characters of the pattern match the empty string? dp[0][0] = true (empty pattern matches empty string). For j >= 1, dp[0][j] = true if and only if p[j-1] == '*' AND dp[0][j-1] is true. In other words, dp[0][j] is true only when every character of p[0..j-1] is a '*'. A single non-star character in the pattern cannot match the empty string, so as soon as any letter or '?' appears, all subsequent dp[0][j] become false for the rest of the row.

This initialization is the most error-prone part of the wildcard DP. A common mistake is to set dp[0][j] = true for all j with p[j-1] == '*' without checking continuity — this incorrectly marks dp[0][j] as true even when a non-star character appeared earlier in the pattern. The correct implementation propagates the true value only while stars are consecutive: once broken by a non-star, the rest of dp[0][j..n] must be false.

For the remaining rows (i >= 1), dp[i][0] = false for all i >= 1, since no non-empty prefix of s can match an empty pattern. These cells are initialized to false by default. Together with the first-row initialization, the table is fully seeded for the main recurrence loops to fill in column-by-column or row-by-row.

Python: 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] = p[j-1] == '*' and dp[0][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 O(m·n), space O(m·n) — reducible to O(n) with a rolling array since each row only depends on the previous row.

Java: public boolean isMatch(String s, String p) { int m = s.length(), n = p.length(); boolean[][] dp = new boolean[m+1][n+1]; dp[0][0] = true; for (int j = 1; j <= n; j++) dp[0][j] = p.charAt(j-1) == '*' && dp[0][j-1]; for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) { if (p.charAt(j-1) == '*') dp[i][j] = dp[i][j-1] || dp[i-1][j]; else if (p.charAt(j-1) == '?' || p.charAt(j-1) == s.charAt(i-1)) dp[i][j] = dp[i-1][j-1]; } return dp[m][n]; } Space can be reduced to O(n) by keeping only prev[] and curr[] arrays and swapping rows each iteration.

Both implementations run in O(m·n) time. The space can be reduced to O(n) using a rolling 1D array: allocate dp[n+1], store the previous-row value before updating, and process columns left-to-right within each row. The rolling array is straightforward here because the '*' transition at dp[i][j] reads dp[i-1][j] (same column, previous row) and dp[i][j-1] (same row, already updated) — a standard pattern for in-place 1D DP optimization.

Regular Expression Matching (LeetCode 10) is the most direct sibling of wildcard matching. The structure is identical — 2D DP, same table dimensions, same base cases — but the '*' transition is more complex because '*' must be paired with the preceding character. Solving wildcard matching first is often recommended as a gentler introduction to the pattern, after which regex matching's added complexity is easier to digest.

Edit Distance (LeetCode 72) uses 2D string DP with a different objective: the minimum number of insertions, deletions, and substitutions to transform one string into another. The dp[i][j] state represents edit distance between prefixes, and the recurrence considers three operations. The first-row and first-column initialization (dp[i][0] = i, dp[0][j] = j) parallels the first-row initialization in wildcard matching — both seed the table with the cost of matching against an empty string.

Interleaving String (LeetCode 97) checks whether string s3 is formed by interleaving s1 and s2. It uses a 2D DP table dp[i][j] = whether s3[0..i+j-1] can be formed from s1[0..i-1] and s2[0..j-1]. Like wildcard matching, it requires careful boundary initialization and a clean recurrence. These three problems — wildcard matching, edit distance, and interleaving string — form the core of the string DP family and together cover nearly every transition pattern that appears in harder string DP problems.