Problem Overview
LeetCode 44 — Wildcard Matching — gives you a string s and a pattern p. Implement pattern matching where ? matches any single character and * matches any sequence of characters (including the empty sequence). The match must cover the entire string.
For example, s = "adceb", p = "*a*b" returns true. The first * matches empty, "a" matches "a", the second * matches "dce", and "b" matches "b". But s = "acdcb", p = "a*c?b" returns false because no valid matching exists.
Two approaches: 2D DP (similar to Regular Expression Matching but simpler star semantics) and a greedy approach with star backtracking (O(s*p) worst case but often linear in practice). Both are accepted interview solutions.
- Input: string s and pattern p
- ? matches exactly one character (any)
- * matches zero or more characters (any sequence)
- Match must cover the entire string
- 2D DP or greedy backtracking approach
Approach 1: 2D Dynamic Programming
Define dp[i][j] = true if s[0..i-1] matches p[0..j-1]. Base case: dp[0][0] = true. First row: dp[0][j] = true only if p[0..j-1] consists entirely of * characters (each * can match empty). First column: dp[i][0] = false for i > 0.
If p[j-1] is a letter: dp[i][j] = dp[i-1][j-1] AND s[i-1] == p[j-1]. If p[j-1] is ?: dp[i][j] = dp[i-1][j-1] (matches any single character). If p[j-1] is *: dp[i][j] = dp[i][j-1] (star matches empty) OR dp[i-1][j] (star absorbs one more character from s).
The star transition is the key difference from regex matching. In regex, * modifies the preceding character. In wildcard, * is standalone and matches any sequence. The transition dp[i-1][j] keeps the * available to absorb more characters.
Star: Empty or Absorb One More
For *, dp[i][j-1] means the star matches nothing (skip it). dp[i-1][j] means the star matches s[i-1] and remains available for more. These two choices cover all possible match lengths: 0, 1, 2, ... characters.
Approach 2: Greedy with Star Backtracking
Use two pointers: si for string position, pi for pattern position. Also track starIdx (last * position in pattern) and matchIdx (string position when the last * was encountered). Iterate while si < len(s).
If characters match (p[pi] == s[si] or p[pi] == ?): advance both pointers. If p[pi] == *: record starIdx = pi, matchIdx = si, advance pi only (star matches empty initially). If no match and starIdx exists: backtrack — pi = starIdx + 1, matchIdx++, si = matchIdx (star absorbs one more character).
If no match and no star to backtrack to: return false. After the string is consumed, check if remaining pattern characters are all *. If yes, return true. This greedy approach is O(s * p) worst case but often linear.
Step-by-Step Walkthrough
Consider s = "adceb", p = "*a*b". DP approach: build 6x5 table. dp[0][0]=T. First row: dp[0][1]=T (p[0]=*). dp[0][2]=F (p[1]=a). dp[0][3]=F, dp[0][4]=F. Row 1 (s[0]=a): dp[1][1]: * → dp[1][0]=F OR dp[0][1]=T → T. dp[1][2]: a==a AND dp[0][1]=T → T.
dp[1][3]: * → dp[1][2]=T OR dp[0][3]=F → T. dp[1][4]: b!=a → F. Row 2 (s[1]=d): dp[2][1]: * → dp[2][0] OR dp[1][1]=T → T. dp[2][2]: d!=a → F. dp[2][3]: * → dp[2][2]=F OR dp[1][3]=T → T. dp[2][4]: b!=d → F.
Continue filling... dp[5][4] (s=adceb, p=*a*b): check s[4]=b, p[3]=b, match: dp[4][3]=T → dp[5][4]=T. Answer: true. The greedy approach: * records star, a matches, * records new star, d/c/e absorbed by second *, b matches final b.
Greedy vs DP Tradeoffs
DP always runs in O(s*p) time. Greedy is often faster (linear) when stars are sparse, but worst case (like s="aaa...a", p="*a*a*a...") is also O(s*p). DP is safer for interviews; greedy impresses if coded correctly.
Implementation in Python and Java
Python DP: dp = [[False]*(n+1) for _ in range(m+1)]. dp[0][0] = True. Fill first row for consecutive stars. Double loop with three-case transition. Return dp[m][n]. About 15 lines.
Python greedy: si = pi = 0. starIdx = matchIdx = -1. While si < len(s): three-case if/elif/else. After loop: while pi < len(p) and p[pi] == "*": pi += 1. Return pi == len(p). About 20 lines.
Java: both approaches translate directly. DP uses boolean[][]. Greedy uses int pointers. The greedy approach in Java is particularly clean due to charAt() and simple pointer arithmetic.
Complexity Analysis
DP: O(s * p) time and O(s * p) space. Each cell is computed once in O(1). Space can be optimized to O(p) with a 1D array since each row depends only on the current and previous rows.
Greedy: O(s * p) worst case. Each star backtrack can advance matchIdx by 1, and si resets to matchIdx. In the worst case, this happens O(s) times with O(p) work each. Best case is O(s + p) when no backtracking occurs.
Both approaches handle the constraints (s, p up to 2000 characters) comfortably. The DP approach is more predictable in runtime; the greedy approach has better average-case performance.
YeetCode Flashcard Tip
Wildcard Matching pairs perfectly with Regular Expression Matching (LeetCode 10). Practice both on YeetCode to see how different star semantics (standalone vs modifier) change the DP transitions.