Wildcard pattern matching
Given a string s and a pattern p, return true if the pattern matches the whole of
s. In the pattern, ? matches exactly one character, * matches any sequence of
characters including the empty one, and any other character matches only itself.
Examples
| Input | Output | Why |
|---|---|---|
s = "adceb", p = "*a*b" | true | The first * matches nothing, the second "dce". |
s = "cb", p = "?a" | false | ? matches c, but a does not match b. |
s = "", p = "*" | true | * matches the empty string. |
Constraints
- 0 ≤ s.length, p.length ≤ 2000
- s: lowercase letters; p: lowercase letters, ? and *
Hints
Hint 1
match[i][j]: does p[:j] match s[:i]?
Hint 2
A star either matches nothing (match[i][j − 1]) or one more character (match[i − 1][j]).
Hint 3
match[0][j] is true only while p[:j] is all stars.
Where people lose marks
- Looping over every length a star could absorb, which is O(n³).
- Initialising match[0][j] to true for all j instead of only for leading stars.
- Confusing * here with the regular-expression * that repeats the previous character.
Dry run on "adceb","*a*b"
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 6s emptyT0T1F2F3F4
Row 0: which prefixes of "*a*b" match "".
-
Step 2 / 6s emptyT0T1F2F3F4s[:1] "a"F0T1T2T3F4
Row 1: which prefixes of "*a*b" match "a".
-
Step 3 / 6s emptyT0T1F2F3F4s[:1] "a"F0T1T2T3F4s[:2] "ad"F0T1F2T3F4
Row 2: which prefixes of "*a*b" match "ad".
-
Step 4 / 6s emptyT0T1F2F3F4s[:1] "a"F0T1T2T3F4s[:2] "ad"F0T1F2T3F4s[:3] "adc"F0T1F2T3F4
Row 3: which prefixes of "*a*b" match "adc".
-
Step 5 / 6s emptyT0T1F2F3F4s[:1] "a"F0T1T2T3F4s[:2] "ad"F0T1F2T3F4s[:3] "adc"F0T1F2T3F4s[:4] "adce"F0T1F2T3F4
Row 4: which prefixes of "*a*b" match "adce".
-
Step 6 / 6s emptyT0T1F2F3F4s[:1] "a"F0T1T2T3F4s[:2] "ad"F0T1F2T3F4s[:3] "adc"F0T1F2T3F4s[:4] "adce"F0T1F2T3F4s[:5] "adceb"F0T1F2T3T4
Row 5: which prefixes of "*a*b" match "adceb". The whole pattern matches.
How to think about it
A two-sequence feasibility table. match[i][j] says whether the first j pattern characters match the first i
string characters. For an ordinary character or ?, the last characters must agree and the prefixes before them
must match: match[i − 1][j − 1]. A * is the interesting case: it matches the empty string
(match[i][j − 1]) or swallows the last character of s while staying available
(match[i − 1][j]). Reading match[i − 1][j] lets one star absorb any number of characters without
a loop over lengths.
Complexity. Time O(|s| · |p|) · Space O(|p|)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def is_match(s, p):
m = len(p)
row = [False] * (m + 1) # row for the empty string
row[0] = True
for j in range(1, m + 1):
row[j] = row[j - 1] and p[j - 1] == '*' # only stars match nothing
for ch in s:
new = [False] * (m + 1)
for j in range(1, m + 1):
if p[j - 1] == '*':
new[j] = new[j - 1] or row[j] # star matches nothing, or one more character
elif p[j - 1] == '?' or p[j - 1] == ch:
new[j] = row[j - 1]
row = new
return row[m]#include <string>
#include <vector>
bool solve(std::string s, std::string p) {
const int m = p.size();
std::vector<bool> row(m + 1, false), next(m + 1, false);
row[0] = true;
for (int j = 1; j <= m; ++j) row[j] = row[j - 1] && p[j - 1] == '*';
for (char ch : s) {
next.assign(m + 1, false);
for (int j = 1; j <= m; ++j) {
if (p[j - 1] == '*') next[j] = next[j - 1] || row[j]; // empty, or absorb ch
else if (p[j - 1] == '?' || p[j - 1] == ch) next[j] = row[j - 1];
}
row.swap(next);
}
return row[m];
}class Solution {
public boolean isMatch(String s, String p) {
int m = p.length();
boolean[] row = new boolean[m + 1];
row[0] = true;
for (int j = 1; j <= m; j++) row[j] = row[j - 1] && p.charAt(j - 1) == '*';
for (char ch : s.toCharArray()) {
boolean[] next = new boolean[m + 1];
for (int j = 1; j <= m; j++) {
char pc = p.charAt(j - 1);
if (pc == '*') next[j] = next[j - 1] || row[j]; // empty, or absorb ch
else if (pc == '?' || pc == ch) next[j] = row[j - 1];
}
row = next;
}
return row[m];
}
}function isMatch(s, p) {
const m = p.length;
let row = new Array(m + 1).fill(false);
row[0] = true;
for (let j = 1; j <= m; j++) row[j] = row[j - 1] && p[j - 1] === '*';
for (const ch of s) {
const next = new Array(m + 1).fill(false);
for (let j = 1; j <= m; j++) {
if (p[j - 1] === '*') next[j] = next[j - 1] || row[j]; // empty, or absorb ch
else if (p[j - 1] === '?' || p[j - 1] === ch) next[j] = row[j - 1];
}
row = next;
}
return row[m];
}fn solve(s: &str, p: &str) -> bool {
let p: Vec<char> = p.chars().collect();
let m = p.len();
let mut row = vec![false; m + 1];
row[0] = true;
for j in 1..=m {
row[j] = row[j - 1] && p[j - 1] == '*';
}
for ch in s.chars() {
let mut next = vec![false; m + 1];
for j in 1..=m {
if p[j - 1] == '*' {
next[j] = next[j - 1] || row[j]; // empty, or absorb ch
} else if p[j - 1] == '?' || p[j - 1] == ch {
next[j] = row[j - 1];
}
}
row = next;
}
row[m]
}solve :: String -> String -> Bool
solve s p = last (foldl step first s)
where
first = scanl (\prev c -> prev && c == '*') True p
-- the row for one more character ch of s, from the previous row
step row ch = scanl cell False (zip3 p row (tail row))
where
cell left (c, diag, up)
| c == '*' = left || up
| c == '?' || c == ch = diag
| otherwise = FalseVariants to try
- Regular expression matching with . and x* (LeetCode 10).
- A greedy two-pointer solution with backtracking to the last star, O(|s| · |p|) worst case but fast in practice.
- Count the ways the pattern can match.
Next problems
How many times one string appears in another
Count the ways to delete characters from s so that what remains is t. Use s's last character for t's last character, or do not.
Open the problem → Medium25 minIs a string an interleaving of two others?
Decide whether s3 can be built by merging s1 and s2, each kept in order. The state is how much of each has been used.
Open the problem → Medium20 minThe shortest common supersequence
The shortest string that contains both strings as subsequences. Every shared character can be written once: n + m − LCS.
Open the problem →Write a solution and run it against the real test table.
Keep going
How many times one string appears in another
Count the ways to delete characters from s so that what remains is t. Use s's last character for t's last character, or do not.
Open the problem → Medium25 minIs a string an interleaving of two others?
Decide whether s3 can be built by merging s1 and s2, each kept in order. The state is how much of each has been used.
Open the problem → Medium20 minThe shortest common supersequence
The shortest string that contains both strings as subsequences. Every shared character can be written once: n + m − LCS.
Open the problem → Dynamic programmingThe pattern behind it
Write the recursion, notice the repeats, fill a table in an order that makes each entry final.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.