Wildcard Matching

Hard Dynamic Programming Strings Original on LeetCode

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 last t matches.

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 <= 2000
  • s has only lowercase English letters.
  • p has 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.

00:00
Testcase

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.

ApproachTimeSpace
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 practiceO(1)

1Brute force (plain recursion)

TimeO(2^(n+m))Every star branches into two calls, and the same (i, j) pairs repeat many times.
SpaceO(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.

  1. If the pattern is used up, succeed only if the text is too.
  2. If p[j] is '*': return match(i, j + 1) or (i < n and match(i + 1, j)).
  3. 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;
    }
}

2Better (bottom-up DP table)

TimeO(n · m)One constant-time step per table cell.
SpaceO(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.

  1. dp[0][0] = true; dp[0][j] = dp[0][j - 1] while p[j - 1] is '*'.
  2. 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]).
  3. Else if p[j - 1] is '?' or equals s[i - 1]: dp[i][j] = dp[i - 1][j - 1].
  4. 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];
    }
}

3Optimal (greedy with star backtracking)

TimeO(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.
SpaceO(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.

  1. i over s, j over p, star = -1, mark = 0.
  2. If p[j] is '?' or equals s[i]: advance both.
  3. Else if p[j] is '*': star = j, mark = i, j++.
  4. Else if star != -1: j = star + 1, mark++, i = mark (the star eats one more character).
  5. 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;
    }
}

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".