A complete visual walkthrough of the 2D dynamic programming approach for pattern matching with '?' and '*'.
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]; } }
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 (m+1) x (n+1) DP table exactly once, doing O(1) work per cell. The table itself requires O(m*n) space.
Space optimization is possible. Since each row only depends on the current and previous row, we can reduce space to O(n) by using two 1D arrays. There's also an O(m+n) greedy two-pointer approach that tracks the last '*' position and backtracks when needed.