Wildcard Matching

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

time O(m*n)space O(m*n)

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.

Details

Animated on: Does pattern "*a*b" match the entire string "adceb"? '?' matches any one character, '*' matches any sequence (including empty).

Problem:Wildcard MatchingHard

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

step 1 / 11

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

-*a*b

-adceb

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

Every step in words

Show all 11 steps

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.
Row 0 means the string is still empty. '*' can match zero characters, so dp[0][1] just inherits dp[0][0] = T.
'a' is not '*', so it demands a real character that an empty string doesn't have — dp[0][2] = F, and it stays F for every column after it too.
Row 0 means the string is still empty. '*' can match zero characters, so dp[0][3] just inherits dp[0][2] = F.
'*' at column 1 has two ways in: absorb one more of "adceb" (dp[0][1] = T, the cell above) or match nothing more (dp[1][0] = F, the cell to the left). Either T makes dp[1][1] = T.
'a' = 'a': the letters agree, so this position costs nothing — dp[1][2] copies the diagonal, dp[0][1] = T.
'*' at column 3 has two ways in: absorb one more of "adceb" (dp[0][3] = F, the cell above) or match nothing more (dp[1][2] = T, the cell to the left). Either T makes dp[1][3] = T.
'b' != 'a' and 'b' is not a wildcard, so there is no arrow in that can save this cell — dp[1][4] = F, no matter what the neighbours say.
'a' != 'd' and 'a' is not a wildcard, so there is no arrow in that can save this cell — dp[2][2] = F, no matter what the neighbours say.
'*' at column 3 has two ways in: absorb one more of "adceb" (dp[1][3] = T, the cell above) or match nothing more (dp[2][2] = F, the cell to the left). Either T makes dp[2][3] = T.
dp[5][4] = T: the whole pattern "*a*b" matches the whole string "adceb". 'b' = 'b': the letters agree, so this position costs nothing — dp[5][4] copies the diagonal, dp[4][3] = T.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Wildcard Matching in the editor All Dynamic Programming problems Back to roadmap