Wildcard string matching (? and *)

Hard

Problem

Return true if the pattern matches the whole string. In the pattern, "?" matches any single character and "*" matches any sequence of characters, including none.

Example 1

Input:  s = "adceb", p = "*a*b"
Output: true

Example 2

Input:  s = "acdcb", p = "a*c?b"
Output: false

Also asked as: String matching where one string contains wildcard characters

Test cases

Case 1

Input:    "adceb", "*a*b"
Expected: true

Case 2

Input:    "acdcb", "a*c?b"
Expected: false

Case 3

Input:    "cb", "?a"
Expected: false

Case 4

Input:    "aa", "a"
Expected: false

Case 5

Input:    "", "*"
Expected: true

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. 2-D DP

Time O(n · m)Space O(n · m)

dp[i][j] = does pattern[..j] match text[..i]. "?" matches any single char; "*" matches empty (dp[i][j-1]) or one-more (dp[i-1][j]).

function isMatch(text, pattern) {
const n = text.length, m = pattern.length;
const dp = Array.from({ length: n + 1 }, () => Array(m + 1).fill(false));
dp[0][0] = true;
for (let j = 1; j <= m; j++) if (pattern[j - 1] === '*') dp[0][j] = dp[0][j - 1];
for (let i = 1; i <= n; i++)
for (let j = 1; j <= m; j++) {
if (pattern[j - 1] === '*') dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
else if (pattern[j - 1] === '?' || pattern[j - 1] === text[i - 1]) dp[i][j] = dp[i - 1][j - 1];
}
return dp[n][m];
}