String matching where one string contains wildcard characters

The problem, simply

You get a text, like adceb, and a pattern, like a*c?b. Normal letters in the pattern must match the same letter in the text. Two symbols are special:

• ? matches exactly one letter, any letter.
• * matches any number of letters in a row, including none at all.

Say true if the pattern can cover the whole text from the first letter to the last. Say false otherwise. Here n is the text length and m is the pattern length.

A story to remember it

Picture it

Examples

Way 1: the simple way

Walk both strings with two fingers, t in the text and p in the pattern, and try every choice.

1. If the pattern is used up, it is a match only if the text is used up too.
2. If the text is used up, it is a match only if every pattern card left is a star.
3. If the card is *, try two things: the star covers nothing (move p), or the star covers one more letter (move t, keep p).
4. If the card is ? or the same letter, move both fingers.
5. Otherwise, fail.

The trouble is that the same question gets asked many times. Here is the tree of questions for text ab and pattern **c. Each node t,p asks: does the text from t match the pattern from p?

class Solution {
    public boolean isMatch(String text, String pattern) {
        return match(text, pattern, 0, 0);
    }

    private boolean match(String text, String pattern, int t, int p) {
        if (p == pattern.length()) return t == text.length();   // no cards left
        if (t == text.length()) {                               // no letters left
            for (int k = p; k < pattern.length(); k++)
                if (pattern.charAt(k) != '*') return false;      // only stars may remain
            return true;
        }
        char card = pattern.charAt(p);
        if (card == '*') {
            return match(text, pattern, t, p + 1)                // star covers nothing
                || match(text, pattern, t + 1, p);               // star covers one more letter
        }
        if (card == '?' || card == text.charAt(t)) {
            return match(text, pattern, t + 1, p + 1);           // one card, one letter
        }
        return false;
    }
}

How long it takes: every star splits the work in two, so in the worst case it is exponential, about O(2^(n + m)). Extra room: the waiting helpers on the call stack, O(n + m).

Way 2: the clever way

Answer every small question once and write it in a chart. dp[i][j] says whether the first i letters of the text can be covered by the first j cards of the pattern. Row 0 and column 0 mean "nothing yet".

1. dp[0][0] = true: no letters, no cards.
2. Top row: with no letters, a card can only be a star that covers nothing. So dp[0][j] = dp[0][j - 1] when card j is *, and false otherwise.
3. For every other box, look at card j and letter i:
   • Card is *: true if the box to the left is true (the star covers nothing) or the box above is true (the star covers this letter too).
   • Card is ? or the same letter: copy the box up and to the left, the diagonal.
   • Otherwise: false.
4. The answer is the bottom right box, dp[n][m].

class Solution {
    public boolean isMatch(String text, String pattern) {
        int n = text.length(), m = pattern.length();
        boolean[][] dp = new boolean[n + 1][m + 1];
        dp[0][0] = true;                                  // nothing covers nothing
        for (int j = 1; j <= m; j++) {
            if (pattern.charAt(j - 1) == '*') dp[0][j] = dp[0][j - 1];  // stars cover nothing
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                char card = pattern.charAt(j - 1);
                char letter = text.charAt(i - 1);
                if (card == '*') {
                    dp[i][j] = dp[i][j - 1]     // left: star covers nothing
                            || dp[i - 1][j];    // up: star covers this letter too
                } else if (card == '?' || card == letter) {
                    dp[i][j] = dp[i - 1][j - 1]; // diagonal: one card, one letter
                }
            }
        }
        return dp[n][m];
    }
}

How long it takes: the chart has (n + 1) * (m + 1) boxes and each takes a constant amount of work, O(n * m). Extra room: the chart, O(n * m). Each row only reads the row above, so you can keep two rows and use O(m).

Watch out for

• Forgetting the top row. A pattern that starts with stars, like **a, must still be able to match a. Without the top row fill, dp[0][1] stays false and everything below breaks.
• Off by one. Box dp[i][j] uses letter text.charAt(i - 1) and card pattern.charAt(j - 1).
• Returning true when the pattern only matches a prefix. The answer is dp[n][m], not "any true in the last column".
• Many stars in a row act like one star. Squashing ** into * first makes the chart smaller.

What interviewers ask next

• Can you use less memory? Keep only the previous row and the current row, O(m) space.
• Is there a faster way in practice? Yes, a greedy scan with two fingers that remembers the last star and how many letters it has eaten. On a mismatch it lets the last star eat one more letter and tries again. It uses O(1) space and is fast on real inputs, though the worst case is still O(n * m).
• Regular expression matching (LeetCode 10), where . is one letter and x* is zero or more of x. Same kind of chart, but a star looks two columns to the left.
• Match many texts against one pattern? Turn the pattern into a small machine (an automaton) once, then run each text through it.

Remember this

Grown-up words: the joker cards are wildcards, the chart is a 2D dynamic programming table, asking the same small question again is overlapping subproblems, and saving the answers is memoization or tabulation.