Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. 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 *.
  2. 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");
    }
}

Solve Wildcard Matching online · All practice problems