Wildcard Matching
Wildcard Matching is a hard dynamic programming problem solved with the strings pattern.
The best approach, optimal (greedy with star backtracking), runs in O(n · m) worst case, near O(n + m) in practice time and O(1) space.
Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (plain recursion) up.
Problem
You are given a text s and a pattern p. The pattern may contain two wildcards:
?matches exactly one character (any character).*matches any sequence of characters, including the empty sequence.
Return true if the pattern matches the entire text, not just a part of it, and false otherwise.
Examples
Example 1
- Input
s = "report", p = "re*t"- Output
true- Why
*absorbs "por", and the lasttmatches.
Example 2
- Input
s = "melon", p = "m?l"- Output
false- Why
- The pattern has three positions and nothing to absorb "on", so it covers only part of the text.
Example 3
- Input
s = "abcabd", p = "*ab?"- Output
true- Why
*takes "abc", then "ab" matches literally and?takes "d".
Constraints
0 <= s.length, p.length <= 2000shas only lowercase English letters.phas only lowercase English letters,?and*.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 18 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (plain recursion) | O(2^(n+m)) | O(n + m) |
| Better (bottom-up DP table) | O(n · m) | O(n · m) |
| Optimal (greedy with star backtracking) | O(n · m) worst case, near O(n + m) in practice | O(1) |
1Brute force (plain recursion)
O(2^(n+m))Every star branches into two calls, and the same (i, j) pairs repeat many times.O(n + m)Recursion depth is at most n + m.Match from the front. A letter or ? must agree with the current character; a * tries both choices: match the empty string (skip the star) or eat one character (keep the star). Without caching the same states are explored again and again.
- If the pattern is used up, succeed only if the text is too.
- If p[j] is '*': return match(i, j + 1) or (i < n and match(i + 1, j)).
- Otherwise the characters must agree (or p[j] is '?'), then recurse on (i + 1, j + 1).
class Solution {
public boolean isMatch(String s, String p) {
return match(s, p, 0, 0);
}
private boolean match(String s, String p, int i, int j) {
if (j == p.length()) return i == s.length();
if (p.charAt(j) == '*')
return match(s, p, i, j + 1) || (i < s.length() && match(s, p, i + 1, j));
if (i < s.length() && (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i)))
return match(s, p, i + 1, j + 1);
return false;
}
}class Solution:
def isMatch(self, s: str, p: str) -> bool:
def match(i: int, j: int) -> bool:
if j == len(p):
return i == len(s)
if p[j] == '*':
return match(i, j + 1) or (i < len(s) and match(i + 1, j))
if i < len(s) and (p[j] == '?' or p[j] == s[i]):
return match(i + 1, j + 1)
return False
return match(0, 0)class Solution {
public:
bool isMatch(string s, string p) {
return match(s, p, 0, 0);
}
private:
bool match(const string& s, const string& p, int i, int j) {
if (j == (int)p.size()) return i == (int)s.size();
if (p[j] == '*')
return match(s, p, i, j + 1) || (i < (int)s.size() && match(s, p, i + 1, j));
if (i < (int)s.size() && (p[j] == '?' || p[j] == s[i]))
return match(s, p, i + 1, j + 1);
return false;
}
};function isMatch(s, p) {
const match = (i, j) => {
if (j === p.length) return i === s.length;
if (p[j] === '*')
return match(i, j + 1) || (i < s.length && match(i + 1, j));
if (i < s.length && (p[j] === '?' || p[j] === s[i]))
return match(i + 1, j + 1);
return false;
};
return match(0, 0);
}2Better (bottom-up DP table)
O(n · m)One constant-time step per table cell.O(n · m)The full (n + 1) x (m + 1) table.Each (i, j) state only depends on smaller prefixes, so fill a boolean table. dp[i][j] is true when the first i text characters match the first j pattern characters.
- dp[0][0] = true; dp[0][j] = dp[0][j - 1] while p[j - 1] is '*'.
- If p[j - 1] is '*': dp[i][j] = dp[i][j - 1] (star matches nothing) or dp[i - 1][j] (star eats s[i - 1]).
- Else if p[j - 1] is '?' or equals s[i - 1]: dp[i][j] = dp[i - 1][j - 1].
- Return dp[n][m].
class Solution {
public boolean isMatch(String s, String p) {
int n = s.length(), m = p.length();
boolean[][] dp = new boolean[n + 1][m + 1];
dp[0][0] = true;
for (int j = 1; j <= m && p.charAt(j - 1) == '*'; j++) dp[0][j] = true;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
char c = p.charAt(j - 1);
if (c == '*') dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
else if (c == '?' || c == s.charAt(i - 1)) dp[i][j] = dp[i - 1][j - 1];
}
}
return dp[n][m];
}
}class Solution:
def isMatch(self, s: str, p: str) -> bool:
n, m = len(s), len(p)
dp = [[False] * (m + 1) for _ in range(n + 1)]
dp[0][0] = True
for j in range(1, m + 1):
if p[j - 1] != '*':
break
dp[0][j] = True
for i in range(1, n + 1):
for j in range(1, m + 1):
c = p[j - 1]
if c == '*':
dp[i][j] = dp[i][j - 1] or dp[i - 1][j]
elif c == '?' or c == s[i - 1]:
dp[i][j] = dp[i - 1][j - 1]
return dp[n][m]class Solution {
public:
bool isMatch(string s, string p) {
int n = s.size(), m = p.size();
vector<vector<bool>> dp(n + 1, vector<bool>(m + 1, false));
dp[0][0] = true;
for (int j = 1; j <= m && p[j - 1] == '*'; j++) dp[0][j] = true;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
char c = p[j - 1];
if (c == '*') dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
else if (c == '?' || c == s[i - 1]) dp[i][j] = dp[i - 1][j - 1];
}
}
return dp[n][m];
}
};function isMatch(s, p) {
const n = s.length, m = p.length;
const dp = Array.from({ length: n + 1 }, () => new Array(m + 1).fill(false));
dp[0][0] = true;
for (let j = 1; j <= m && p[j - 1] === '*'; j++) dp[0][j] = true;
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= m; j++) {
const c = p[j - 1];
if (c === '*') dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
else if (c === '?' || c === s[i - 1]) dp[i][j] = dp[i - 1][j - 1];
}
}
return dp[n][m];
}3Optimal (greedy with star backtracking)
O(n · m) worst case, near O(n + m) in practiceEach backtrack moves `mark` forward by one, and the pattern part after the star is re-scanned at most n times.O(1)Only four integer pointers.Walk both strings with two pointers. When a * appears, remember where it is and let it match nothing for now. On a later mismatch, go back to the most recent star and let it eat one more text character. Only the latest star ever needs to be revisited, because it can absorb anything an earlier star could.
- i over s, j over p, star = -1, mark = 0.
- If p[j] is '?' or equals s[i]: advance both.
- Else if p[j] is '*': star = j, mark = i, j++.
- Else if star != -1: j = star + 1, mark++, i = mark (the star eats one more character).
- Else return false. After s is consumed, skip trailing stars and check j reached the end of p.
class Solution {
public boolean isMatch(String s, String p) {
int i = 0, j = 0, star = -1, mark = 0;
int n = s.length(), m = p.length();
while (i < n) {
if (j < m && (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i))) {
i++;
j++;
} else if (j < m && p.charAt(j) == '*') {
star = j;
mark = i;
j++;
} else if (star != -1) {
j = star + 1;
mark++;
i = mark;
} else {
return false;
}
}
while (j < m && p.charAt(j) == '*') j++;
return j == m;
}
}class Solution:
def isMatch(self, s: str, p: str) -> bool:
i = j = 0
star, mark = -1, 0
n, m = len(s), len(p)
while i < n:
if j < m and (p[j] == '?' or p[j] == s[i]):
i += 1
j += 1
elif j < m and p[j] == '*':
star, mark = j, i
j += 1
elif star != -1:
j = star + 1
mark += 1
i = mark
else:
return False
while j < m and p[j] == '*':
j += 1
return j == mclass Solution {
public:
bool isMatch(string s, string p) {
int i = 0, j = 0, star = -1, mark = 0;
int n = s.size(), m = p.size();
while (i < n) {
if (j < m && (p[j] == '?' || p[j] == s[i])) {
i++;
j++;
} else if (j < m && p[j] == '*') {
star = j;
mark = i;
j++;
} else if (star != -1) {
j = star + 1;
mark++;
i = mark;
} else {
return false;
}
}
while (j < m && p[j] == '*') j++;
return j == m;
}
};function isMatch(s, p) {
let i = 0, j = 0, star = -1, mark = 0;
const n = s.length, m = p.length;
while (i < n) {
if (j < m && (p[j] === '?' || p[j] === s[i])) {
i++;
j++;
} else if (j < m && p[j] === '*') {
star = j;
mark = i;
j++;
} else if (star !== -1) {
j = star + 1;
mark++;
i = mark;
} else {
return false;
}
}
while (j < m && p[j] === '*') j++;
return j === m;
}Edge cases to test
- Empty text with a pattern of only stars (matches)
- Empty pattern with a non-empty text (no match)
- Several stars in a row behave like one star
- A star must sometimes take more than the shortest piece, e.g. text "aab" with pattern "*ab"
Hints
Hint 1
Think about the decision at a *: it either matches nothing, or it eats one character and stays active.
Hint 2
Let dp[i][j] mean "the first i characters of s match the first j characters of p".
Hint 3
You can avoid the table: remember the position of the last star and how much text it has eaten, and retry from there when a mismatch happens.
FAQ
What is the best time complexity for Wildcard Matching?
Optimal (greedy with star backtracking) runs in O(n · m) worst case, near O(n + m) in practice time and O(1) extra space. Each backtrack moves `mark` forward by one, and the pattern part after the star is re-scanned at most n times.
Which pattern does Wildcard Matching use?
It is a dynamic programming problem that uses the strings pattern. Other problems with the same pattern: Edit Distance, Longest Common Subsequence, Longest Palindromic Subsequence.
Is there a brute force solution for Wildcard Matching?
Yes. Brute force (plain recursion) takes O(2^(n+m)) time and O(n + m) space. Match from the front.
Which edge cases should I test for Wildcard Matching?
Empty text with a pattern of only stars (matches); Empty pattern with a non-empty text (no match); Several stars in a row behave like one star; A star must sometimes take more than the shortest piece, e.g. text "aab" with pattern "ab".