Practice › Dynamic Programming
Wildcard Matching
Hard · Dynamic Programming · Asked at Google, Amazon, Microsoft, Meta, Adobe
In the pattern, ? matches any single character and * matches any sequence of characters (including the empty one). Does the pattern match the entire string? Print YES or NO.
Input
First line: the string s (lowercase letters). Second line: the pattern p (lowercase letters, ?, *).
Output
YES or NO.
Constraints
- 1 ≤ |s|, |p| ≤ 2000
match[i][j] for s[0..i) and p[0..j): a letter or ? needs match[i−1][j−1]; a * is match[i][j−1] (empty) or match[i−1][j] (eat one more character).
Example 1
Input
aa a
Output
NO
Example 2
Input
adceb *a*b
Output
YES
Hints
- match[i][j] = does p[0..j) match s[0..i)? match[0][0] = true; an empty string matches a pattern prefix only if it is all *.
- For "*": match[i][j−1] (it matches nothing) or match[i−1][j] (it absorbs s[i−1]). For "?" or a letter: match[i−1][j−1] and the characters agree.
Approach
Fill the table row by row over the string. The * transition reuses the same column in the previous row, letting one star swallow any number of characters. Keep only two rows. Greedy backtracking also works, but the DP is easier to prove correct.
Complexity: O(|s| · |p|) time · O(|p|) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
string s, p;
cin >> s >> p;
int n = s.size(), m = p.size();
vector<char> prev(m + 1, 0), cur(m + 1, 0);
prev[0] = 1;
for (int j = 1; j <= m; j++) prev[j] = prev[j - 1] && p[j - 1] == '*';
for (int i = 1; i <= n; i++) {
cur[0] = 0;
for (int j = 1; j <= m; j++) {
if (p[j - 1] == '*') cur[j] = cur[j - 1] || prev[j];
else cur[j] = prev[j - 1] && (p[j - 1] == '?' || p[j - 1] == s[i - 1]);
}
swap(prev, cur);
}
cout << (prev[m] ? "YES" : "NO") << "\n";
return 0;
}Python solution
import sys
s, p = sys.stdin.read().split()[:2]
m = len(p)
prev = [False] * (m + 1)
prev[0] = True
for j in range(1, m + 1):
prev[j] = prev[j - 1] and p[j - 1] == "*"
for c in s:
cur = [False] * (m + 1)
for j in range(1, m + 1):
if p[j - 1] == "*":
cur[j] = cur[j - 1] or prev[j]
else:
cur[j] = prev[j - 1] and p[j - 1] in ("?", c)
prev = cur
print("YES" if prev[m] else "NO")Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.next(), p = sc.next();
int n = s.length(), m = p.length();
boolean[] prev = new boolean[m + 1], cur = new boolean[m + 1];
prev[0] = true;
for (int j = 1; j <= m; j++) prev[j] = prev[j - 1] && p.charAt(j - 1) == '*';
for (int i = 1; i <= n; i++) {
cur[0] = false;
for (int j = 1; j <= m; j++) {
char pc = p.charAt(j - 1);
if (pc == '*') cur[j] = cur[j - 1] || prev[j];
else cur[j] = prev[j - 1] && (pc == '?' || pc == s.charAt(i - 1));
}
boolean[] t = prev; prev = cur; cur = t;
}
System.out.println(prev[m] ? "YES" : "NO");
}
}