Example: Wildcard Matching Dynamic Programming in C++

// Wildcard Matching Dynamic Programming
#include <iostream>
#include <string>
#include <vector>

// Function to check if string s matches pattern p using dynamic programming
bool isMatchDP(const std::string& s, const std::string& p) {
    int m = s.length();
    int n = p.length();

    // dp[i][j] will be true if the first i characters of s match
    // the first j characters of p.
    std::vector<std::vector<bool>> dp(m + 1, std::vector<bool>(n + 1, false));

    // Base Case 1: Empty string and empty pattern match
    dp[0][0] = true;

    // Base Case 2: Empty string s can match patterns consisting only of '*'
    // e.g., s = "", p = "***" => true
    for (int j = 1; j <= n; ++j) {
        if (p[j - 1] == '*') {
            dp[0][j] = dp[0][j - 1]; // '*' matches an empty sequence
        }
    }

    // Fill the DP table
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            // Case 1: Current pattern character is '*'
            if (p[j - 1] == '*') {
                // '*' matches an empty sequence (dp[i][j-1]) OR
                // '*' matches the current character in s (dp[i-1][j])
                dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
            }
            // Case 2: Current pattern character is '?' or matches current string character
            else if (p[j - 1] == '?' || s[i - 1] == p[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            }
            // Case 3: No match (dp[i][j] remains false)
        }
    }

    return dp[m][n];
}

int main() {
    // Step 1: Define test cases
    std::string s1 = "adceb";
    std::string p1 = "*a*b"; // Expected: true

    std::string s2 = "acdcb";
    std::string p2 = "a*c?b"; // Expected: false

    std::string s3 = "aa";
    std::string p3 = "a"; // Expected: false

    std::string s4 = "aa";
    std::string p4 = "*"; // Expected: true

    std::string s5 = "ab";
    std::string p5 = "?*"; // Expected: true

    std::string s6 = "mississippi";
    std::string p6 = "mis*is*p*?"; // Expected: false

    // Step 2: Test the DP function
    std::cout << "Test 1 (\"" << s1 << "\", \"" << p1 << "\"): "
              << (isMatchDP(s1, p1) ? "true" : "false") << std::endl;
    std::cout << "Test 2 (\"" << s2 << "\", \"" << p2 << "\"): "
              << (isMatchDP(s2, p2) ? "true" : "false") << std::endl;
    std::cout << "Test 3 (\"" << s3 << "\", \"" << p3 << "\"): "
              << (isMatchDP(s3, p3) ? "true" : "false") << std::endl;
    std::cout << "Test 4 (\"" << s4 << "\", \"" << p4 << "\"): "
              << (isMatchDP(s4, p4) ? "true" : "false") << std::endl;
    std::cout << "Test 5 (\"" << s5 << "\", \"" << p5 << "\"): "
              << (isMatchDP(s5, p5) ? "true" : "false") << std::endl;
    std::cout << "Test 6 (\"" << s6 << "\", \"" << p6 << "\"): "
              << (isMatchDP(s6, p6) ? "true" : "false") << std::endl;

    return 0;
}