Wildcard string matching (? and *)
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
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];}