A complete visual walkthrough of the 2D dynamic programming approach for pattern matching with '?' and '*'.
Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*' where:
'?' Matches any single character.'*' Matches any sequence of characters (including the empty sequence).The matching should cover the entire input string (not partial).
Example 1:
Input: s = "aa", p = "a" Output: false Explanation: "a" does not match the entire string "aa".
Example 2:
Input: s = "aa", p = "*" Output: true Explanation: '*' matches any sequence.
Example 3:
Input: s = "cb", p = "?a" Output: false Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.
Constraints:
0 <= s.length, p.length <= 2000s contains only lowercase English letters.p contains only lowercase English letters, '?' or '*'.The most natural approach tries to match character by character, branching when we encounter *:
Overlapping subproblems! The recursive solution recomputes "does s[i..] match p[j..]?" many times. This is the classic signal for dynamic programming — store results in a table.
Define dp[i][j] = whether s[0..i-1] matches p[0..j-1]. We build a table of size (m+1) x (n+1).
dp[i][j] = dp[i-1][j-1]dp[i][j] = dp[i][j-1] (match empty) OR dp[i-1][j] (match one more char)dp[0][0] = true (empty matches empty). dp[0][j] = true if p[0..j-1] is all '*'s.The '*' transition is the key. When '*' matches empty, we look left (dp[i][j-1]). When '*' matches one more character, we look up (dp[i-1][j]) — the '*' stays available to match even more characters. This elegantly captures "match any sequence."
Let's trace the DP table for s = "adceb" and p = "*a*b".
Green cells are true. The answer is at dp[5][4] (bottom-right).
| "" | * | a | * | b | |
|---|---|---|---|---|---|
| "" | T | T | F | F | F |
| a | F | T | T | T | F |
| d | F | T | F | T | F |
| c | F | T | F | T | F |
| e | F | T | F | T | F |
| b | F | T | F | T | T |
dp[5][4] = true — "adceb" matches "*a*b".
dp[0][j] = true for all j, and '*' transitions propagate true values down every column.class Solution { public boolean isMatch(String s, String p) { int m = s.length(), n = p.length(); boolean[][] dp = new boolean[m + 1][n + 1]; // Base case: empty string matches empty pattern dp[0][0] = true; // Base case: empty string can match leading '*'s for (int j = 1; j <= n; j++) if (p.charAt(j - 1) == '*') dp[0][j] = dp[0][j - 1]; // Fill the DP table for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (p.charAt(j - 1) == '*') // '*' matches empty (left) or one more char (up) dp[i][j] = dp[i][j - 1] || dp[i - 1][j]; else if (p.charAt(j - 1) == '?' || s.charAt(i - 1) == p.charAt(j - 1)) // Exact match or '?' — carry diagonal dp[i][j] = dp[i - 1][j - 1]; } } return dp[m][n]; } }
func isMatch(s string, p string) bool { m, n := len(s), len(p) dp := make([][]bool, m+1) for i := range dp { dp[i] = make([]bool, n+1) } // Base case: empty string matches empty pattern dp[0][0] = true // Base case: empty string can match leading '*'s for j := 1; j <= n; j++ { if p[j-1] == '*' { dp[0][j] = dp[0][j-1] } } // Fill the DP table for i := 1; i <= m; i++ { for j := 1; j <= n; j++ { if p[j-1] == '*' { // '*' matches empty (left) or one more char (up) dp[i][j] = dp[i][j-1] || dp[i-1][j] } else if p[j-1] == '?' || s[i-1] == p[j-1] { // Exact match or '?' — carry diagonal dp[i][j] = dp[i-1][j-1] } } } return dp[m][n] }
def is_match(s: str, p: str) -> bool: m, n = len(s), len(p) dp = [[False] * (n + 1) for _ in range(m + 1)] # Base case: empty string matches empty pattern dp[0][0] = True # Base case: empty string can match leading '*'s for j in range(1, n + 1): if p[j - 1] == "*": dp[0][j] = dp[0][j - 1] # Fill the DP table for i in range(1, m + 1): for j in range(1, n + 1): if p[j - 1] == "*": # '*' matches empty (left) or one more char (up) dp[i][j] = dp[i][j - 1] or dp[i - 1][j] elif p[j - 1] == "?" or s[i - 1] == p[j - 1]: # Exact match or '?' — carry diagonal dp[i][j] = dp[i - 1][j - 1] return dp[m][n]
impl Solution { pub fn is_match(s: String, p: String) -> bool { let sb = s.as_bytes(); let pb = p.as_bytes(); let (m, n) = (sb.len(), pb.len()); let mut dp = vec![vec![false; n + 1]; m + 1]; // Base case: empty string matches empty pattern dp[0][0] = true; // Base case: empty string can match leading '*'s for j in 1..=n { if pb[j-1] == b'*' { dp[0][j] = dp[0][j-1]; } } // Fill the DP table for i in 1..=m { for j in 1..=n { if pb[j-1] == b'*' { // '*' matches empty (left) or one more char (up) dp[i][j] = dp[i][j-1] || dp[i-1][j]; } else if pb[j-1] == b'?' || sb[i-1] == pb[j-1] { // Exact match or '?' — carry diagonal dp[i][j] = dp[i-1][j-1]; } } } dp[m][n] } }
function isMatch(s: string, p: string): boolean { const m = s.length, n = p.length; const dp: boolean[][] = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(false)); // Base case: empty string matches empty pattern dp[0][0] = true; // Base case: empty string can match leading '*'s for (let j = 1; j <= n; j++) if (p[j - 1] === "*") dp[0][j] = dp[0][j - 1]; // Fill the DP table for (let i = 1; i <= m; i++) { for (let j = 1; j <= n; j++) { if (p[j - 1] === "*") // '*' matches empty (left) or one more char (up) dp[i][j] = dp[i][j - 1] || dp[i - 1][j]; else if (p[j - 1] === "?" || s[i - 1] === p[j - 1]) // Exact match or '?' — carry diagonal dp[i][j] = dp[i - 1][j - 1]; } } return dp[m][n]; }
Enter a string and pattern, then step through the DP table cell by cell or run all at once.
We fill every cell in the (n+1) × (m+1) DP table exactly once (where n = string length, m = pattern length), doing O(1) work per cell. The table itself requires O(n × m) space. Space can be reduced to O(m) by using two rolling columns, since each row only depends on the current and previous row.
Each '*' branches into two recursive calls: match empty or consume one character. With up to n+m characters and wildcards, the recursion tree can double at every level, producing O(2n+m) nodes. Stack depth is bounded by n + m.
A 2D DP table of size (n+1) × (m+1) is filled row by row. Each cell does O(1) work -- checking one character match or one OR operation for '*'. The table itself requires O(n × m) space, reducible to O(m) with rolling rows.
* matches any sequence -- the DP recurrence for * elegantly combines "skip star" (dp[i][j-1]) and "star matches one more char" (dp[i-1][j]). This captures zero-or-more matching without exponential branching.
Review these before coding to avoid predictable interview regressions.
Wrong move: An incomplete state merges distinct subproblems and caches incorrect answers.
Usually fails on: Correctness breaks on cases that differ only in hidden state.
Fix: Define state so each unique subproblem maps to one DP cell.