Pattern visualizer

Wildcard Matching

dp[i][j] asks whether the first j characters of the pattern match the first i characters of the string. A literal or '?' can only copy the diagonal cell, because it consumes exactly one character from each side. A '*' is different: it can vanish and match nothing (copy the cell to its left, same row) or swallow one more character of the string and stay in play (copy the cell above, same column) — so its truth is the OR of both. That single OR is why a '*' cell keeps its T even while every literal cell beneath it has gone F. Animated on: Does pattern "*a*b" match the entire string "adceb"? '?' matches any one character, '*' matches any sequence (including empty)..

'?' copies the diagonal, '*' takes the OR of the cell above and the cell to the left

time O(m*n)space O(m*n)step 1 / 11

dp[i][j] = does "*a*b"[0..j) match "adceb"[0..i)

-*a*b

-adceb

line 2

An empty pattern matches an empty string, so dp[0][0] = T. Rows track how much of "adceb" has been consumed, columns how much of "*a*b" has.

Pseudocode

1FUNCTION wildcardMatch(s, p):
2  dp[0][0] <- TRUE
3  FOR j FROM 1 TO LENGTH(p)
4    dp[0][j] <- dp[0][j-1] AND p[j-1] = '*'
5  FOR i FROM 1 TO LENGTH(s)
6    FOR j FROM 1 TO LENGTH(p)
7      IF p[j-1] = '*'
8        dp[i][j] <- dp[i-1][j] OR dp[i][j-1]
9      ELSE IF p[j-1] = '?' OR p[j-1] = s[i-1]
10        dp[i][j] <- dp[i-1][j-1]
11      ELSE
12        dp[i][j] <- FALSE
13  RETURN dp[LENGTH(s)][LENGTH(p)]

← / → step · space play · Home restart

Where to practice Dynamic Programming

Practice Dynamic Programming problems All Dynamic Programming problems Back to roadmap