DP 34: Wildcard Matching | Recursive to 1D Array Optimisation

This chapter covers the final and most intricate problem in the Dynamic Programming on Strings series: Wildcard Matching. We will systematically transition from a brute-force recursive approach to memoization, full tabulation, and finally optimal 1D space optimization.

1. Problem Statement & Core Rules

You are given two strings:

1. s1 (Pattern): Can contain lowercase English letters, question marks (?), and asterisks (*).
2. s2 (Text): Contains only lowercase English letters.

Your task is to determine if string s1 can fully match string s2.

The Special Wildcard Characters

• Question Mark (?): Matches any single character unconditionally.
• Asterisk (*): Matches any sequence of characters of length zero or more.

Real-Life Analogy: The Flexible Matchmaker

Note: Think of string matching as a security checkpoint supervisor matching an expected pattern template (s1) against an incoming traveler document (s2). Regular letters require exact spelling matches. A ? is a wildcard token that acts as a universal placeholder for any single letter. A * acts like an accordion or a sponge: it can absorb zero letters (disappear entirely), absorb one letter, or soak up an entire sequence of consecutive letters (like def) until the rest of the pattern lines up.

2. Walkthrough Examples

Let's examine four concrete test cases to internalize how ? and * behave under different conditions:

Example 1: Basic Question Mark Match

• Pattern (s1): ?ey
• Text (s2): rey
• Walkthrough:
  • y matches y.
  • e matches e.
  • ? matches r (since question mark matches any single character).
• Result: true

Example 2: Asterisk Absorbing a Sequence

• Pattern (s1): ab*cd
• Text (s2): abdefcd
• Walkthrough:
  • d matches d, c matches c.
  • * absorbs the entire sequence def (length 3).
  • a matches a, b matches b.
• Result: true

Example 3: Multiple Empty-Absorbing Asterisks

• Pattern (s1): **abcd
• Text (s2): abcd
• Walkthrough:
  • d matches d, c matches c, b matches b, a matches a.
  • Both * characters match sequences of length 0 (essentially vanishing).
• Result: true

Example 4: Mismatch Failure Case

• Pattern (s1): ab?d
• Text (s2): abcc
• Walkthrough:
  • a matches a, b matches b.
  • ? matches c.
  • However, pattern character d fails to match text character c.
• Result: false

3. Why Standard String Matching Fails for Asterisks (*)

In previous string matching problems (like LCS or Edit Distance), decisions were deterministic. Here, when you encounter an asterisk *, you face a profound branching dilemma:

Pattern: ab * cd
Text:    ab d e f c d
          ^

When standing at *, how many characters in the text should the asterisk consume?

• Should it consume 0 characters (skip * and match b with something else)?
• Should it consume 1 character (f)?
• Should it consume 2 characters (ef)?
• Should it consume 3 characters (def)?

Because you cannot know the correct consumption length a priori, you must explore all possible choices via recursion.

4. Approach 1: Recursive Formulation

Defining the Recursive State

We define a recursive function f(i, j) which signifies:

Does the substring of pattern s1 from index 0 to i match the substring of text s2 from index 0 to j?

Transition Logic

At any state (i, j), we check the characters at s1[i] and s2[j]:

1. Match or Question Mark (?): If s1[i] == s2[j] or s1[i] == '?', both characters match successfully. We shrink both pointers:

   C++

   Copy

   return f(i - 1, j - 1);
   

2. Asterisk (*): An asterisk gives us two primary choices:

   • Choice A (Treat * as empty): Skip the asterisk and keep the text pointer j stationary: f(i - 1, j)
   • Choice B (Treat * as consuming one character): Keep the asterisk i stationary, but consume one character from text by moving j backwards: f(i, j - 1)
   C++

   Copy

   return f(i - 1, j) || f(i, j - 1);
   

3. General Mismatch: If characters do not match and s1[i] is neither ? nor *, return false.

Recursive Code Implementation

class Solution {
public:
    bool f(int i, int j, string &p, string &t) {
        // Base Cases
        if (i < 0 && j < 0) return true;
        if (i < 0 && j >= 0) return false;
        if (j < 0 && i >= 0) {
            // If text is exhausted, pattern must contain only '*'
            for (int ii = 0; ii <= i; ii++) {
                if (p[ii] != '*') return false;
            }
            return true;
        }

        // Match or Question Mark
        if (p[i] == t[j] || p[i] == '?') {
            return f(i - 1, j - 1, p, t);
        }

        // Asterisk Branching
        if (p[i] == '*') {
            return f(i - 1, j, p, t) || f(i, j - 1, p, t);
        }

        return false; // Mismatch
    }

    bool isMatch(string p, string t) {
        int n = p.size(), m = t.size();
        return f(n - 1, m - 1, p, t);
    }
};

5. Approach 2: Memoization (Top-Down DP)

Because overlapping subproblems occur repeatedly during recursive branching, we memoize our results in a 2D table dp[n][m].

Memoization Code

class Solution {
public:
    bool f(int i, int j, string &p, string &t, vector<vector<int>> &dp) {
        if (i < 0 && j < 0) return true;
        if (i < 0 && j >= 0) return false;
        if (j < 0 && i >= 0) {
            for (int ii = 0; ii <= i; ii++) {
                if (p[ii] != '*') return false;
            }
            return true;
        }

        if (dp[i][j] != -1) return dp[i][j];

        if (p[i] == t[j] || p[i] == '?') {
            return dp[i][j] = f(i - 1, j - 1, p, t, dp);
        }

        if (p[i] == '*') {
            return dp[i][j] = f(i - 1, j, p, t, dp) || f(i, j - 1, p, t, dp);
        }

        return dp[i][j] = false;
    }

    bool isMatch(string p, string t) {
        int n = p.size(), m = t.size();
        vector<vector<int>> dp(n, vector<int>(m, -1));
        return f(n - 1, m - 1, p, t, dp);
    }
};

• Time Complexity: $O(N \times M)$
• Space Complexity: $O(N \times M)$ [DP table] + $O(N + M)$ [Auxiliary Stack Space]

6. Approach 3: Tabulation (Bottom-Up DP)

To eliminate recursion stack overhead, we convert our solution to tabulation using 1-based indexing to cleanly handle negative base cases.

Tabulated Code Implementation

class Solution {
public:
    bool isMatch(string p, string t) {
        int n = p.size();
        int m = t.size();
        
        vector<vector<bool>> dp(n + 1, vector<bool>(m + 1, false));
        
        // Base Case 1: Both strings empty
        dp[0][0] = true;
        
        // Base Case 2: Text is empty (j = 0), pattern has leading stars
        for (int i = 1; i <= n; i++) {
            bool flag = true;
            for (int ii = 1; ii <= i; ii++) {
                if (p[ii - 1] != '*') {
                    flag = false;
                    break;
                }
            }
            dp[i][0] = flag;
        }
        
        // Fill the DP table
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (p[i - 1] == t[j - 1] || p[i - 1] == '?') {
                    dp[i][j] = dp[i - 1][j - 1];
                } 
                else if (p[i - 1] == '*') {
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                } 
                else {
                    dp[i][j] = false;
                }
            }
        }
        
        return dp[n][m];
    }
};

7. Approach 4: Space Optimization (1D Array)

Notice that computing row i in our DP table only requires values from the previous row (i - 1) and the current row (i). We can optimize our space complexity from $O(N \times M)$ down to $O(M)$ using two 1D arrays (prev and curr).

Space-Optimized Code Implementation

class Solution {
public:
    bool isMatch(string p, string t) {
        int n = p.size();
        int m = t.size();
        
        vector<bool> prev(m + 1, false);
        vector<bool> curr(m + 1, false);
        
        prev[0] = true; // dp[0][0] = true
        
        for (int j = 1; j <= m; j++) {
            prev[j] = false;
        }
        
        for (int i = 1; i <= n; i++) {
            // Initialize current row base case for j = 0
            bool flag = true;
            for (int ii = 1; ii <= i; ii++) {
                if (p[ii - 1] != '*') {
                    flag = false;
                    break;
                }
            }
            curr[0] = flag;
            
            for (int j = 1; j <= m; j++) {
                if (p[i - 1] == t[j - 1] || p[i - 1] == '?') {
                    curr[j] = prev[j - 1];
                } 
                else if (p[i - 1] == '*') {
                    curr[j] = prev[j] || curr[j - 1];
                } 
                else {
                    curr[j] = false;
                }
            }
            prev = curr;
        }
        
        return prev[m];
    }
};

8. Summary & Key Takeaways

• Core Wildcard Logic: Question marks ? match exact single characters; asterisks * branch into empty-absorption (i-1, j) and character-consumption (i, j-1).
• Base Case Initialization: When text s2 is empty (j = 0), the pattern s1 can only match if it consists exclusively of asterisks (*).
• Index Shifting: Converting recursive negative base checks into 1-based indexing in tabulation simplifies boundary management.
• Space Reduction: Row-dependency in string DP allows space reduction from 2D grids to rolling 1D arrays.