Wildcard Matching - CPP Solution

1. Introduction

In this blog post, we tackle the Wildcard Matching problem, a classic problem in computer science that involves string pattern matching. This problem is a great example to understand dynamic programming in C++ as it involves matching an input string with a pattern containing wildcard characters.

Problem

Given an input string s and a pattern p, implement wildcard pattern matching with support for two special characters:

- '?' which matches any single character.

- '*' which matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string, not just a partial match.

2. Solution Steps

1. Use dynamic programming to build a solution matrix.

2. Initialize the first row and column based on the pattern.

3. Iterate over each character of the string and the pattern.

4. If characters match or the pattern has '?', propagate the diagonal value.

5. If the pattern has '*', consider it as an empty sequence or match one character from the string.

6. After filling the matrix, the bottom-right cell contains the result.

3. Code Program

#include <iostream>
#include <vector>
using namespace std;

// Function to implement wildcard pattern matching
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; // Empty string and empty pattern are a match

    // Handle patterns starting with '*'
    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] == '?' || s[i - 1] == p[j - 1]) {
                // Propagate the diagonal value
                dp[i][j] = dp[i - 1][j - 1];
            } else if (p[j - 1] == '*') {
                // '*' matches an empty sequence or one character
                dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
            }
        }
    }
    return dp[m][n]; // Result in the bottom-right cell
}

int main() {
    string s = "adceb";
    string p = "*a*b";
    cout << "Is match: " << isMatch(s, p) << endl;
    return 0;
}

Output:

Is match: 1

Explanation:

1. The input string "adceb" and the pattern "*a*b" are processed.

2. The dynamic programming matrix is used to store the match status at each step.

3. The pattern '*' is treated as an empty sequence or matches one character from the string.

4. '?' matches any single character, and the matrix is updated accordingly.

5. The final value at the bottom-right of the matrix indicates the match result.

6. In this case, the function returns true (represented as 1), confirming that the pattern matches the entire string.