☕ DSA Java Articles

Topics › Dynamic Programming › DP on Strings

Wildcard matching

Hard TUF ID 314 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given a string s and a pattern p. The pattern may contain ordinary letters and two wildcards:

Return true if the pattern matches the whole of s, not just a part of it.

Constraints (LeetCode 44): 0 ≤ |s|, |p| ≤ 2000, s has lowercase letters, p has lowercase letters, ? and *.

Example 1

s = "adceb", p = "*a*b"
answer = true       // first * matches "", a matches a, second * matches "dce", b matches b

Example 2

s = "acdcb", p = "a*c?b"
answer = false      // after a, the pattern needs ...c?b at the end, but s ends in "dcb"

Example 3

s = "aa", p = "a"
answer = false      // the pattern covers only the first character

These are file-name globs, not regular expressions. In a regex, * repeats the previous token; here * stands on its own and matches anything.

The recurrence

Write f(i, j) for “does the string prefix s[0..i) match the pattern prefix p[0..j)?”. Base cases:

For i, j > 0, look at the last pattern character pc = p[j - 1]:

  1. pc is ? or equals s[i - 1]. It consumes exactly that character, so f(i, j) = f(i - 1, j - 1).
  2. pc is *. It matches some number k ≥ 0 of trailing characters of s. Instead of looping over k, split into two cases:
    • k = 0: the star matches nothing and disappears, giving f(i, j - 1).
    • k ≥ 1: the star swallows s[i - 1] and stays in the pattern, so it can swallow more. That is f(i - 1, j).

    So f(i, j) = f(i, j - 1) || f(i - 1, j).

  3. Otherwise pc is a different letter, and f(i, j) = false.

The star case is the heart of the problem. Unrolling f(i - 1, j) again and again gives f(i - 1, j - 1), f(i - 2, j - 1), and so on, which is exactly “the star matches 1, 2, … characters”. Keeping the star in place turns an O(n) loop per state into two constant-time lookups.

Approach 1: Recursion

Intuition. Write the recurrence directly. The order of the base cases matters: test j == 0 first so that f(0, 0) is true, then handle i == 0 by checking that the remaining pattern is all stars.

Algorithm.

  1. If j == 0, return i == 0.
  2. If i == 0, return whether p[0..j) contains only *.
  3. Apply the three cases above.
static boolean recursive(String s, String p) {
    return solve(s.length(), p.length(), s, p);
}

/** Does the prefix s[0..i) match the pattern prefix p[0..j)? */
static boolean solve(int i, int j, String s, String p) {
    if (j == 0) return i == 0;                               // empty pattern matches only the empty string
    if (i == 0) return allStars(p, j);                       // empty string: the pattern must be all '*'
    char pc = p.charAt(j - 1);
    if (pc == '?' || pc == s.charAt(i - 1)) return solve(i - 1, j - 1, s, p);
    if (pc == '*') return solve(i, j - 1, s, p)              // the star matches nothing
                       || solve(i - 1, j, s, p);             // the star swallows s[i - 1] and may continue
    return false;                                            // two different letters
}

/** True when p[0..j) consists only of '*'. */
static boolean allStars(String p, int j) {
    for (int k = 0; k < j; k++) if (p.charAt(k) != '*') return false;
    return true;
}

Complexity. Time exponential: every star can branch two ways, and a pattern like "*a*a*a*b" against a long string of as explores a huge number of ways to distribute the characters among the stars. Space O(n + m) for the recursion stack.

Approach 2: Memoization

Intuition. The result depends only on (i, j), so there are (n + 1)(m + 1) distinct subproblems. The exponential blow-up comes from reaching the same pair through different star splits, so caching each answer fixes it. A boolean[][] cannot tell “not computed” from false, so the table stores 0 for unknown, 1 for false and 2 for true.

Algorithm.

  1. Create int dp[n + 1][m + 1], all zeros.
  2. Run the recursion, returning the cached value when dp[i][j] != 0, and storing ok ? 2 : 1 after computing.
static boolean memoization(String s, String p) {
    int[][] dp = new int[s.length() + 1][p.length() + 1];
    return memo(s.length(), p.length(), s, p, dp);
}

static boolean memo(int i, int j, String s, String p, int[][] dp) {
    if (j == 0) return i == 0;
    if (i == 0) return allStars(p, j);
    if (dp[i][j] != 0) return dp[i][j] == 2;
    char pc = p.charAt(j - 1);
    boolean ok;
    if (pc == '?' || pc == s.charAt(i - 1)) ok = memo(i - 1, j - 1, s, p, dp);
    else if (pc == '*') ok = memo(i, j - 1, s, p, dp) || memo(i - 1, j, s, p, dp);
    else ok = false;
    dp[i][j] = ok ? 2 : 1;
    return ok;
}

Complexity. Time O(n · m) for the states. The all-star check at i == 0 is not cached, but it is reached at most twice per cell of row 1, adding at most O(m^2). Space O(n · m) plus O(n + m) stack.

Approach 3: Tabulation

Intuition. Cell (i, j) reads the diagonal (i - 1, j - 1), the cell above (i - 1, j) and the cell to the left (i, j - 1). Filling rows top to bottom and each row left to right makes all three ready. Row 0 is filled with a running “all stars so far” flag, dp[0][j] = dp[0][j - 1] && p[j - 1] == '*', which also removes the O(m^2) base-case cost of the memoized version. Column 0 below row 0 stays false.

Algorithm.

  1. dp[0][0] = true; fill row 0 with the running star flag.
  2. For i = 1 .. n, j = 1 .. m: diagonal for ? or a matching letter; left OR above for *; otherwise false.
  3. Return dp[n][m].
static boolean tabulation(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; j++) dp[0][j] = dp[0][j - 1] && p.charAt(j - 1) == '*';
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            char pc = p.charAt(j - 1);
            if (pc == '?' || pc == s.charAt(i - 1)) dp[i][j] = dp[i - 1][j - 1];
            else if (pc == '*') dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
            else dp[i][j] = false;
        }
    }
    return dp[n][m];
}

Dry run on Example 1 (s = "adceb" down the side, p = "*a*b" across, T = true):

  ”” * a * b
”” T T F F F
a F T T T F
d F T F T F
c F T F T F
e F T F T F
b F T F T T

The first * column is all true: a leading star can absorb any prefix. The bold T in row a is the letter match a = a, inherited diagonally from (0, 1). The second * column then stays true all the way down, because each cell reads the true value above it (the star swallowing one more character). Finally b matches b and takes the diagonal value from row e, column *.

Complexity. Time O(n · m), space O(n · m).

Approach 4: Space optimized

Intuition. Each row reads only the previous row and itself, so two arrays suffice. Build row 0 into prev, then for each character of s fill cur and swap. Because the arrays are reused, cur[0] must be reset to false at the start of every row; after the first swap cur is the old row 0, whose cur[0] is true.

Algorithm.

  1. Fill prev as row 0.
  2. For each i = 1 .. n: set cur[0] = false, fill cur[1..m], swap.
  3. Return prev[m].
static boolean spaceOptimized(String s, String p) {
    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;                                      // a non-empty string never matches an empty pattern
        for (int j = 1; j <= m; j++) {
            char pc = p.charAt(j - 1);
            if (pc == '?' || pc == s.charAt(i - 1)) cur[j] = prev[j - 1];
            else if (pc == '*') cur[j] = cur[j - 1] || prev[j];
            else cur[j] = false;
        }
        boolean[] tmp = prev; prev = cur; cur = tmp;
    }
    return prev[m];
}

Complexity. Time O(n · m), space O(m).

Approach 5: Greedy with backtracking to the last star

Intuition. Stars split the pattern into star-free segments, like a and b in *a*b. Match each segment at the earliest place it fits in s. Matching earlier never hurts, because it leaves more of s for what follows, and the next star can always absorb the gap. So when a mismatch happens we never need to revisit an older star. We only let the most recent star swallow one more character and retry the segment after it. If there is no star to fall back on, the match fails.

Algorithm.

  1. Pointers i in s and j in p. star = -1 is the position of the last * seen, mark is where in s that star’s match ends.
  2. While i < |s|:
    • If p[j] is ? or equals s[i], advance both.
    • Else if p[j] is *, record star = j, mark = i, and advance j only (the star matches nothing for now).
    • Else if a star exists, backtrack: j = star + 1, mark++, i = mark (the star swallows one more character).
    • Else return false.
  3. Skip trailing stars in p; return whether j reached the end of p.
static boolean greedy(String s, String p) {
    int i = 0, j = 0, star = -1, mark = 0;                   // star = index of the last '*', mark = where it started in s
    while (i < s.length()) {
        if (j < p.length() && (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i))) {
            i++;
            j++;
        } else if (j < p.length() && p.charAt(j) == '*') {
            star = j++;                                      // first let the star match nothing
            mark = i;
        } else if (star != -1) {
            j = star + 1;                                    // stuck: let the last star swallow one more character
            i = ++mark;
        } else {
            return false;
        }
    }
    while (j < p.length() && p.charAt(j) == '*') j++;        // trailing stars can match the empty rest
    return j == p.length();
}

Dry run on Example 1 (s = "adceb", p = "*a*b"):

step i j action
1 0 0 *: star = 0, mark = 0, j = 1
2 0 1 a = a: i = 1, j = 2
3 1 2 *: star = 2, mark = 1, j = 3
4 1 3 b ≠ d: backtrack, mark = 2, i = 2, j = 3
5 2 3 b ≠ c: backtrack, mark = 3, i = 3, j = 3
6 3 3 b ≠ e: backtrack, mark = 4, i = 4, j = 3
7 4 3 b = b: i = 5, j = 4

s is used up, there are no trailing stars to skip, and j = 4 = |p|, so the answer is true. The first star was never revisited once the second star appeared.

Complexity. Time O(n · m) in the worst case: each backtrack advances mark by one and may rescan a segment of length up to m. On typical inputs it is close to linear. Space O(1). This is the approach to use when memory matters; the DP versions are easier to adapt to variants such as counting matches.

Edge cases and pitfalls