Wildcard Matching

hard string dp greedy

Problem

Match input string s against pattern p that supports two wildcards: '?' matches any single character and '*' matches any sequence of characters (possibly empty). The match must cover the entire input string.

Let dp[i][j] mean s[..i] matches p[..j]. The interesting case is '*': it can either consume one more character (dp[i−1][j]) or match the empty sequence here (dp[i][j−1]).

Inputs = "adceb", p = "*a*b"

Outputtrue

def is_match(s, p):
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True
    for j in range(1, n + 1):
        if p[j - 1] == "*":
            dp[0][j] = dp[0][j - 1]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j - 1] == "*":
                dp[i][j] = dp[i - 1][j] or dp[i][j - 1]
            elif p[j - 1] == "?" or p[j - 1] == s[i - 1]:
                dp[i][j] = dp[i - 1][j - 1]
    return dp[m][n]

function isMatch(s, p) {
  const m = s.length, n = p.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(false));
  dp[0][0] = true;
  for (let j = 1; j <= n; j++) if (p[j - 1] === "*") dp[0][j] = dp[0][j - 1];
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (p[j - 1] === "*") dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
      else if (p[j - 1] === "?" || p[j - 1] === s[i - 1]) dp[i][j] = dp[i - 1][j - 1];
    }
  }
  return dp[m][n];
}

class Solution {
    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++) {
                if (p.charAt(j - 1) == '*') dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                else if (p.charAt(j - 1) == '?' || p.charAt(j - 1) == s.charAt(i - 1)) dp[i][j] = dp[i - 1][j - 1];
            }
        }
        return dp[m][n];
    }
}

bool isMatch(string s, string p) {
    int m = s.size(), n = p.size();
    vector<vector<bool>> dp(m + 1, 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 - 1][j] || dp[i][j - 1];
            else if (p[j - 1] == '?' || p[j - 1] == s[i - 1]) dp[i][j] = dp[i - 1][j - 1];
        }
    }
    return dp[m][n];
}

Explanation

We match string s against a pattern with '?' (any one character) and '*' (any sequence, including empty). The table dp[i][j] answers: does the first i chars of s match the first j chars of p?

We seed dp[0][0] = true (empty matches empty). The first row handles leading '*'s, which can match an empty string, so dp[0][j] = dp[0][j-1] when p[j-1] is '*'.

The interesting case is '*': it can either match empty (carry over dp[i][j-1]) or consume one more character of s (carry over dp[i-1][j]). We OR these two: dp[i][j] = dp[i-1][j] || dp[i][j-1].

For a literal letter or '?' that matches the current character, we just inherit the diagonal dp[i-1][j-1]. A mismatch stays false.

Example: s = "adceb", p = "*a*b". The first * swallows the empty start, a matches, the second * swallows "dce", and b matches the end → dp[5][4] = true.

Time: O(m · n) Space: O(m · n)