The O(n) Club: Wildcard Matching: How to Outsmart Your Inner Greedy Asterisk

The O(n) Club: Wildcard Matching—How to Outsmart Your Inner Greedy Asterisk

⚡ TL;DR

This isn’t regex, it’s chaos—Wildcard Matching means matching a string against a pattern filled with ? (one mystery char) and * (zero, one, infinite: your call). Brute-forcing? Prepare for pain. DP = less caffeine, less fire. See how in Java:

// Does s match pattern p using '?' and '*'? 
public boolean isMatch(String s, String p) {
    int m = s.length(), n = p.length();
    boolean[][] dp = new boolean[m + 1][n + 1];
    dp[0][0] = true;
    for (int j = 1; j <= n; j++) {
        if (p.charAt(j-1) == '*') dp[0][j] = dp[0][j-1];
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            char pc = p.charAt(j-1);
            if (pc == '*') dp[i][j] = dp[i-1][j] || dp[i][j-1];
            else if (pc == '?' || pc == s.charAt(i-1)) dp[i][j] = dp[i-1][j-1];
        }
    }
    return dp[m][n];
}

🧠 How Devs Usually Mess This Up

Common mistake: treat * like it must eat something—like it’s afraid of being empty (spoiler: it’s not). Also, piling up consecutive * like you’re building a sandcastle: it only needs one to swallow everything. Or the classic: try every possible split by hand, discover exponential sadness. And if you forget that * can match absolutely nothing? Yeah, “off by one” errors get promoted to “off by all.”

🔍 What’s Actually Going On

* is the gluten of pattern symbols—it expands to fill any space, including zero; ? is more modest, handling only one character at a time. The trick is to use DP: you ask, “Has this chunk of string matched this chunk of pattern yet?” and store your answer. If you see *, you can ignore it (dp[i][j-1]—let it be empty) or let it eat a character from the string (dp[i-1][j]). Both work. Your job is to keep the wildcards in line without breaking the table.

🛠️ PseudoCode

• Make a DP table:
  

  boolean[][] dp = new boolean[s.length()+1][p.length()+1];

  Each spot means: “Did these first X chars match these first Y in the pattern?”
• Initialize the base cases:
  

  dp[0][0] = true; // empty matches empty
  for (int j=1; j<=p.length(); j++)
      if (p[j-1] == '*') dp[0][j] = dp[0][j-1];

  Empty string can only be matched if the pattern so far is a wall of asterisks.
• Fill the rest:
  

  if (p[j-1] == '*') dp[i][j] = dp[i][j-1] || dp[i-1][j];
  else if (p[j-1] == '?' || p[j-1] == s[i-1]) dp[i][j] = dp[i-1][j-1];
  

  One clause for greedy havoc, one for cool matches.
• Final answer?
  

  return dp[s.length()][p.length()];

  Check the bottom-right for full coverage.

💻 The Code

public boolean isMatch(String s, String p) {
    int m = s.length(), n = p.length();
    boolean[][] dp = new boolean[m + 1][n + 1];
    dp[0][0] = true;
    for (int j = 1; j <= n; j++) {
        if (p.charAt(j - 1) == '*') {
            dp[0][j] = dp[0][j - 1];
        }
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            char pc = p.charAt(j - 1);
            if (pc == '*') {
                dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
            } else if (pc == '?' || pc == s.charAt(i - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            }
        }
    }
    return dp[m][n];
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Stacking *s? Collapse them—Java will thank you with less memory drama.
• Skip the dp[0][j] base case and say goodbye to matching empty strings with *.
• If you forget * means zero or more, “almost right” turns into “always wrong.”
• Time: O(mn). Space: O(mn). Optimize if you love pain or have something to prove.

🧠 Interviewer Brain-Tattoo

If * feels greedy, that’s because it’s a cosmic vacuum—let it hoover up characters, but stay in control with DP. “In wildcard matching, laziness is a feature. Use it wisely.”