Pattern matcher with wildcards

You are halfway through an Uber phone screen when the interviewer asks, "Given a string and a pattern with ? and * wildcards, can you determine if the pattern matches the entire string?" The catch: * can match any sequence of characters, including nothing at all. This problem, also known as Wildcard Matching on other platforms, is a staple of hard-level DP interviews at companies like Google, Amazon, and Adobe. It forces you to reason carefully about what "match zero or more characters" really means in terms of subproblem structure.

TL;DR

Build a 2D boolean DP table where dp[i][j] represents whether the first i characters of the string match the first j characters of the pattern. For each cell, apply one of three rules: if the pattern character is *, combine dp[i][j-1] (match zero chars) with dp[i-1][j] (match one or more). If it is ? or an exact letter match, carry forward dp[i-1][j-1]. The answer lives in dp[m][n]. Time and space are both O(m * n).

Why This Problem Matters

Wildcard matching sits at the intersection of string processing and dynamic programming. It shows up regularly at Uber, Google, Amazon, Adobe, and Oracle. Beyond interviews, the same DP structure appears in file system glob patterns, database LIKE queries, and network routing rules. If you can build the intuition for how * consumes characters, you will find related DP problems like regex matching and edit distance much more approachable.

Understanding the Problem

We are given two strings: an input string s containing only lowercase letters, and a pattern p containing lowercase letters plus two special characters:

• ? matches exactly one character (any character)
• * matches any sequence of characters, including an empty sequence

The goal is to determine whether p matches the entirety of s.

Let's look at a few examples:

Edge Cases to Consider

1. Both empty: "" matches "" (true)
2. Empty string, only stars: "" matches "*" (true, since * can match empty)
3. Empty string, non-star pattern: "" does not match "a" (false)
4. Exact match: "abcde" matches "abcde" (true)
5. All question marks: "abcde" matches "?????" (true, lengths match)

Solution Approach

Why Brute Force Fails

A naive recursive approach tries every possible expansion of each *. For a pattern like "*a*b*c*d" against a long string, the number of branches grows exponentially because each * can consume anywhere from zero to all remaining characters. Without memoization, you end up re-solving the same subproblems many times.

The DP Insight

Instead of guessing how many characters each * should consume, we can break the problem into subproblems. Define dp[i][j] as: "Does s[0..i-1] match p[0..j-1]?" If we can fill this table correctly, the answer is simply dp[m][n] where m = len(s) and n = len(p).

The Three Transition Rules

Every cell dp[i][j] falls into one of three cases based on p[j-1]:

1. Exact match or ?: If p[j-1] equals s[i-1], or p[j-1] is ?, then dp[i][j] = dp[i-1][j-1]. Both characters are consumed together.

2. Star matches zero characters: If p[j-1] is *, the star might match nothing. In that case dp[i][j] = dp[i][j-1], skipping the star entirely.

3. Star matches one or more characters: If p[j-1] is *, the star might consume s[i-1] and potentially more. In that case dp[i][j] = dp[i-1][j], consuming one character from s while keeping the star available for further matching.

For *, we combine rules 2 and 3 with OR: dp[i][j] = dp[i][j-1] || dp[i-1][j].

Base Cases

• dp[0][0] = true: empty string matches empty pattern
• dp[0][j]: only true if every character in p[0..j-1] is * (each star matches empty)
• dp[i][0] for i > 0: always false (non-empty string cannot match empty pattern)

Watching the DP Table Fill

Let's trace through s = "adceb", p = "*a*b". The rows represent characters of s (with an empty-string row at top), and the columns represent characters of p (with an empty-pattern column at left). Step through the animation to see how each cell is computed:

The final cell dp[5][4] is true, confirming the match. Notice how column 1 (the first *) stays true all the way down, because * can absorb any prefix of the string.

Now let's look at a non-matching case. For s = "cb", p = "?a":

Here dp[2][2] is false. The ? matched c fine, but b does not equal a, so the overall match fails.

Implementation

Prefer a different language? Jump to solutions in other languages.

public class Solution {
  public boolean isMatch(String s, String p) {
    int sLen = s.length();
    int pLen = p.length();
    boolean[][] dp = new boolean[sLen + 1][pLen + 1];
    dp[0][0] = true;

    // Handle leading '*' characters in the pattern
    for (int j = 1; j <= pLen; j++) {
      if (p.charAt(j - 1) == '*') {
        dp[0][j] = dp[0][j - 1];
      }
    }

    // Fill the DP table
    for (int i = 1; i <= sLen; i++) {
      for (int j = 1; j <= pLen; j++) {
        if (p.charAt(j - 1) == '*') {
          // '*' matches zero chars (left) or one+ chars (above)
          dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
        } else if (p.charAt(j - 1) == '?' || s.charAt(i - 1) == p.charAt(j - 1)) {
          // Exact match or '?' wildcard
          dp[i][j] = dp[i - 1][j - 1];
        }
      }
    }

    return dp[sLen][pLen];
  }
}

Let's walk through the key sections:

1. Initialization: We create a (sLen + 1) x (pLen + 1) table, all false by default, and set dp[0][0] = true.

2. First row fill: We scan through the pattern. As long as we see *, we carry forward true from the left. The moment we hit a non-star character, all remaining first-row cells stay false.

3. Main loop: For each pair (i, j), we check the pattern character and apply the appropriate rule. The * case is an OR of two possibilities. The ?/exact case copies the diagonal.

4. Result: dp[sLen][pLen] tells us whether the full string matches the full pattern.

Complexity Analysis

Time Complexity: O(m * n)

We fill an (m+1) x (n+1) table where m is the length of the string and n is the length of the pattern. Each cell takes O(1) to compute: a character comparison plus one or two table lookups.

Space Complexity: O(m * n)

The DP table itself requires O(m * n) space. You can optimize this to O(n) by keeping only two rows (current and previous), since each row only depends on the row above it and the current row's left neighbor. In an interview, start with the 2D version for clarity, then mention the optimization.

Alternative Approaches

1. Top-down memoization: Same O(m * n) complexity, but uses recursion with a hash map or 2D memo array. Easier to derive from the recursive definition but risks stack overflow on very long inputs.

2. Greedy two-pointer: Track the position of the last * and backtrack when a mismatch occurs. Uses O(1) space but is harder to prove correct. Worth mentioning to show breadth of knowledge.

Common Pitfalls

1. Forgetting the first-row initialization: Without handling leading * characters, patterns like "*a" will fail on valid inputs. The first row must propagate true through consecutive * characters.

2. Confusing * with regex *: In regex, * means "zero or more of the preceding element." Here, * is standalone and matches any sequence. Do not accidentally implement regex semantics.

3. Off-by-one indexing: The DP table is 1-indexed (row 0 and column 0 represent empty strings), but s and p are 0-indexed. Always access s.charAt(i - 1) and p.charAt(j - 1), not s.charAt(i).

4. Missing the OR for *: The star case requires dp[i][j-1] || dp[i-1][j]. Forgetting either branch will cause incorrect results for patterns where * needs to match zero characters or needs to match multiple characters.

Interview Tips

When solving this problem in an interview:

1. Clarify assumptions: "Can * match an empty sequence?" (yes). "Are there only lowercase letters in s?" (yes). "Can p contain characters other than lowercase, ?, and *?" (no).

2. Draw the table: Sketch a small 3x3 or 4x4 DP table on the whiteboard. Label rows with string characters and columns with pattern characters. Fill a few cells to show your interviewer the logic.

3. State the recurrence clearly: "If the pattern character is *, I OR two cells. Otherwise, I check the diagonal." This one sentence captures the entire algorithm.

4. Mention optimizations: After coding, note that space can be reduced to O(n) with a rolling array, and mention the greedy approach as an alternative.

5. Test with edge cases: Run through ("", "*"), ("", ""), and ("a", "?") to verify boundary behavior.

Key Takeaways

• The core insight is that * gives you two choices at each position: consume zero characters (look left in the DP table) or consume one character and stay on the same * (look up).
• The ? wildcard and exact character matches both use the same diagonal transition dp[i-1][j-1], just like classic string matching.
• Initializing the first row correctly is critical. Consecutive leading * characters can all match empty, but a single non-star character breaks the chain.
• This 2D DP pattern transfers directly to related problems like regex matching and edit distance. Master it once, and you have a template for an entire category of string DP problems.
• Always start with the O(m * n) space solution in interviews for clarity, then discuss the O(n) optimization to demonstrate engineering depth.

Practice Makes Perfect

Once you are comfortable with wildcard matching, these related problems will reinforce the same DP patterns:

• Pattern Driven String Matcher (regex-style matching with . and *)
• String Transformation Cost (edit distance, another 2D string DP)
• Sentence Formation with Word Dictionary (string segmentation with DP)
• Longest Substring Without Repeated Characters (sliding window on strings)

This problem and hundreds of others are available on Firecode, where over 50,000 engineers have prepared for technical interviews and landed roles at top tech companies. Whether you are targeting Uber, Google, or Amazon, building fluency with 2D DP problems like this one will pay dividends across your entire interview preparation.

Solutions in Other Languages

Python

class Solution:
    def is_match(self, s: str, p: str) -> bool:
        dp = [[False] * (len(p) + 1) for _ in range(len(s) + 1)]
        dp[0][0] = True

        for j in range(1, len(p) + 1):
            if p[j - 1] == '*':
                dp[0][j] = dp[0][j - 1]

        for i in range(1, len(s) + 1):
            for j in range(1, len(p) + 1):
                if p[j - 1] == '*':
                    dp[i][j] = dp[i][j - 1] or dp[i - 1][j]
                elif p[j - 1] == '?' or s[i - 1] == p[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]

        return dp[len(s)][len(p)]

JavaScript

class Solution {
  isMatch(s, p) {
    const dp = Array(s.length + 1).fill(false).map(() => Array(p.length + 1).fill(false));
    dp[0][0] = true;

    for (let j = 1; j <= p.length; j++) {
      if (p[j - 1] === '*') {
        dp[0][j] = dp[0][j - 1];
      }
    }

    for (let i = 1; i <= s.length; i++) {
      for (let j = 1; j <= p.length; j++) {
        if (p[j - 1] === '*') {
          dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
        } else if (p[j - 1] === '?' || s[i - 1] === p[j - 1]) {
          dp[i][j] = dp[i - 1][j - 1];
        }
      }
    }

    return dp[s.length][p.length];
  }
}

TypeScript

class Solution {
  isMatch(s: string, p: string): boolean {
    const dp: boolean[][] = Array(s.length + 1).fill(false).map(() => Array(p.length + 1).fill(false));
    dp[0][0] = true;

    for (let j = 1; j <= p.length; j++) {
      if (p[j - 1] === '*') {
        dp[0][j] = dp[0][j - 1];
      }
    }

    for (let i = 1; i <= s.length; i++) {
      for (let j = 1; j <= p.length; j++) {
        if (p[j - 1] === '*') {
          dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
        } else if (p[j - 1] === '?' || s[i - 1] === p[j - 1]) {
          dp[i][j] = dp[i - 1][j - 1];
        }
      }
    }

    return dp[s.length][p.length];
  }
}

C++

#include <vector>
#include <string>

class Solution {
public:
  bool isMatch(std::string &s, std::string &p) {
    int m = s.size();
    int n = p.size();
    std::vector<std::vector<bool>> dp(m + 1, std::vector<bool>(n + 1, false));
    dp[0][0] = true;

    for (int j = 1; j <= n; ++j) {
      if (p[j - 1] == '*') {
        dp[0][j] = dp[0][j - 1];
      }
    }

    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        if (p[j - 1] == '*') {
          dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
        } else if (p[j - 1] == '?' || s[i - 1] == p[j - 1]) {
          dp[i][j] = dp[i - 1][j - 1];
        }
      }
    }

    return dp[m][n];
  }
};

Go

func (sol *Solution) IsMatch(s string, p string) bool {
    dp := make([][]bool, len(s)+1)
    for i := range dp {
        dp[i] = make([]bool, len(p)+1)
    }
    dp[0][0] = true

    for j := 1; j <= len(p); j++ {
        if p[j-1] == '*' {
            dp[0][j] = dp[0][j-1]
        }
    }

    for i := 1; i <= len(s); i++ {
        for j := 1; j <= len(p); j++ {
            if p[j-1] == '*' {
                dp[i][j] = dp[i][j-1] || dp[i-1][j]
            } else if p[j-1] == '?' || s[i-1] == p[j-1] {
                dp[i][j] = dp[i-1][j-1]
            }
        }
    }

    return dp[len(s)][len(p)]
}

Scala

class Solution {
  def isMatch(s: String, p: String): Boolean = {
    val dp = Array.ofDim[Boolean](s.length + 1, p.length + 1)
    dp(0)(0) = true

    for (j <- 1 to p.length) {
      if (p(j - 1) == '*') {
        dp(0)(j) = dp(0)(j - 1)
      }
    }

    for (i <- 1 to s.length) {
      for (j <- 1 to p.length) {
        if (p(j - 1) == '?' || p(j - 1) == s(i - 1)) {
          dp(i)(j) = dp(i - 1)(j - 1)
        } else if (p(j - 1) == '*') {
          dp(i)(j) = dp(i)(j - 1) || dp(i - 1)(j)
        }
      }
    }

    dp(s.length)(p.length)
  }
}

Kotlin

class Solution {
  fun isMatch(s: String, p: String): Boolean {
    val sLen = s.length
    val pLen = p.length
    val dp = Array(sLen + 1) { BooleanArray(pLen + 1) }
    dp[0][0] = true

    for (j in 1..pLen) {
      if (p[j - 1] == '*') {
        dp[0][j] = dp[0][j - 1]
      }
    }

    for (i in 1..sLen) {
      for (j in 1..pLen) {
        if (p[j - 1] == '*') {
          dp[i][j] = dp[i][j - 1] || dp[i - 1][j]
        } else if (p[j - 1] == '?' || s[i - 1] == p[j - 1]) {
          dp[i][j] = dp[i - 1][j - 1]
        }
      }
    }

    return dp[sLen][pLen]
  }
}

Ruby

class Solution
  def is_match(s, p)
    s_len = s.length
    p_len = p.length
    dp = Array.new(s_len + 1) { Array.new(p_len + 1, false) }
    dp[0][0] = true

    (1..p_len).each do |j|
      if p[j - 1] == '*'
        dp[0][j] = dp[0][j - 1]
      end
    end

    (1..s_len).each do |i|
      (1..p_len).each do |j|
        if p[j - 1] == '*'
          dp[i][j] = dp[i][j - 1] || dp[i - 1][j]
        elsif p[j - 1] == '?' || s[i - 1] == p[j - 1]
          dp[i][j] = dp[i - 1][j - 1]
        end
      end
    end

    dp[s_len][p_len]
  end
end

Rust

impl Solution {
    pub fn is_match(&self, s: String, p: String) -> bool {
        let s_len = s.len();
        let p_len = p.len();
        let mut dp = vec![vec![false; p_len + 1]; s_len + 1];
        dp[0][0] = true;

        let s_bytes = s.as_bytes();
        let p_bytes = p.as_bytes();

        for j in 1..=p_len {
            if p_bytes[j - 1] == b'*' {
                dp[0][j] = dp[0][j - 1];
            }
        }

        for i in 1..=s_len {
            for j in 1..=p_len {
                if p_bytes[j - 1] == b'*' {
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                } else if p_bytes[j - 1] == b'?' || s_bytes[i - 1] == p_bytes[j - 1] {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }

        dp[s_len][p_len]
    }
}

Swift

class Solution {
    func isMatch(_ s: String, _ p: String) -> Bool {
        let sChars = Array(s)
        let pChars = Array(p)
        let sLen = sChars.count
        let pLen = pChars.count
        var dp = Array(repeating: Array(repeating: false, count: pLen + 1), count: sLen + 1)
        dp[0][0] = true

        for j in 1..<pLen + 1 {
            if pChars[j - 1] == Character("*") {
                dp[0][j] = dp[0][j - 1]
            }
        }

        for i in 1..<sLen + 1 {
            for j in 1..<pLen + 1 {
                if pChars[j - 1] == Character("*") {
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j]
                } else if pChars[j - 1] == Character("?") || sChars[i - 1] == pChars[j - 1] {
                    dp[i][j] = dp[i - 1][j - 1]
                }
            }
        }

        return dp[sLen][pLen]
    }
}

C#

public class Solution {
    public bool isMatch(string s, string p) {
        int sLen = s.Length;
        int pLen = p.Length;
        var dp = new bool[sLen + 1, pLen + 1];
        dp[0, 0] = true;

        for (int j = 1; j <= pLen; j++) {
            if (p[j - 1] == '*') {
                dp[0, j] = dp[0, j - 1];
            }
        }

        for (int i = 1; i <= sLen; i++) {
            for (int j = 1; j <= pLen; j++) {
                if (p[j - 1] == '*') {
                    dp[i, j] = dp[i, j - 1] || dp[i - 1, j];
                } else if (p[j - 1] == '?' || s[i - 1] == p[j - 1]) {
                    dp[i, j] = dp[i - 1, j - 1];
                }
            }
        }

        return dp[sLen, pLen];
    }
}

Dart

class Solution {
  bool isMatch(String s, String p) {
    int sLen = s.length;
    int pLen = p.length;
    List<List<bool>> dp = List.generate(sLen + 1, (_) => List.filled(pLen + 1, false));
    dp[0][0] = true;

    for (int j = 1; j <= pLen; j++) {
      if (p[j - 1] == '*') {
        dp[0][j] = dp[0][j - 1];
      }
    }

    for (int i = 1; i <= sLen; i++) {
      for (int j = 1; j <= pLen; j++) {
        if (p[j - 1] == '*') {
          dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
        } else if (p[j - 1] == '?' || s[i - 1] == p[j - 1]) {
          dp[i][j] = dp[i - 1][j - 1];
        }
      }
    }

    return dp[sLen][pLen];
  }
}

PHP

class Solution {
    public function isMatch(string $s, string $p): bool {
        $sLen = strlen($s);
        $pLen = strlen($p);
        $dp = array_fill(0, $sLen + 1, array_fill(0, $pLen + 1, false));
        $dp[0][0] = true;

        for ($j = 1; $j <= $pLen; $j++) {
            if ($p[$j - 1] === '*') {
                $dp[0][$j] = $dp[0][$j - 1];
            }
        }

        for ($i = 1; $i <= $sLen; $i++) {
            for ($j = 1; $j <= $pLen; $j++) {
                if ($p[$j - 1] === '*') {
                    $dp[$i][$j] = $dp[$i][$j - 1] || $dp[$i - 1][$j];
                } elseif ($p[$j - 1] === '?' || $s[$i - 1] === $p[$j - 1]) {
                    $dp[$i][$j] = $dp[$i - 1][$j - 1];
                }
            }
        }

        return $dp[$sLen][$pLen];
    }
}