Dynamic Programming • Strings

Wildcard Matching

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'.

Overview

This is a classic 2D DP problem. The `?` matches any single character. The `*` is the tricky part—it matches ANY sequence of characters (including the empty sequence).

The DP Table

`dp[i][j]` is `true` if the first `i` characters of `s` match the first `j` characters of `p`. We pad the strings with a 1-indexed approach to handle empty string base cases elegantly.

The Exact Match ('?')

If the characters match exactly, or if the pattern character is `?`, then `dp[i][j]` simply takes the value from diagonally above-left: `dp[i-1][j-1]`.

The Star Power ('*')

If the pattern is `*`, it can either act as empty (`dp[i][j-1]`), or it can swallow the current character of `s` and remain active for the next (`dp[i-1][j]`).

	""	'*'	'a'
""	F	F	F
'b'	F	F	F
'a'	F	F	F
'a'	F	F	F

Code Tracker

:::

1let dp = Array.from({ length: N + 1 }, () => new Array(M + 1).fill(false));

2dp[0][0] = true;

3// Base case: matching empty string with '*'

4for (let j = 1; j <= M; j++) {

5 if (p[j - 1] === '*') dp[0][j] = dp[0][j - 1];

6}

7for (let i = 1; i <= N; i++) {

8 for (let j = 1; j <= M; j++) {

9 if (p[j - 1] === s[i - 1] || p[j - 1] === '?') {

10 dp[i][j] = dp[i - 1][j - 1];

11 } else if (p[j - 1] === '*') {

12 dp[i][j] = dp[i - 1][j] || dp[i][j - 1];

13 }

14 }

15}

16return dp[N][M];