Example: Wildcard Matching Recursive in C++

// Wildcard Matching Recursive
#include <iostream>
#include <string>
#include <vector>

// Function to check if string s matches pattern p using recursion
bool isMatchRecursive(const std::string& s, const std::string& p, int s_idx, int p_idx) {
    // Base Case 1: If both pattern and string are exhausted, it's a match.
    if (p_idx == p.length()) {
        return s_idx == s.length();
    }

    // Base Case 2: If string is exhausted but pattern still has characters
    // Only a match if remaining pattern consists solely of '*'
    if (s_idx == s.length()) {
        for (int i = p_idx; i < p.length(); ++i) {
            if (p[i] != '*') {
                return false;
            }
        }
        return true;
    }

    // Case 1: Current pattern character is '*'
    if (p[p_idx] == '*') {
        // Option A: '*' matches an empty sequence (advance pattern)
        // Option B: '*' matches the current character in s (advance string)
        return isMatchRecursive(s, p, s_idx, p_idx + 1) ||
               isMatchRecursive(s, p, s_idx + 1, p_idx);
    }
    // Case 2: Current pattern character is '?' or matches current string character
    else if (p[p_idx] == '?' || s[s_idx] == p[p_idx]) {
        return isMatchRecursive(s, p, s_idx + 1, p_idx + 1);
    }
    // Case 3: No match
    else {
        return false;
    }
}

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 recursive function
    std::cout << "Test 1 (\"" << s1 << "\", \"" << p1 << "\"): "
              << (isMatchRecursive(s1, p1, 0, 0) ? "true" : "false") << std::endl;
    std::cout << "Test 2 (\"" << s2 << "\", \"" << p2 << "\"): "
              << (isMatchRecursive(s2, p2, 0, 0) ? "true" : "false") << std::endl;
    std::cout << "Test 3 (\"" << s3 << "\", \"" << p3 << "\"): "
              << (isMatchRecursive(s3, p3, 0, 0) ? "true" : "false") << std::endl;
    std::cout << "Test 4 (\"" << s4 << "\", \"" << p4 << "\"): "
              << (isMatchRecursive(s4, p4, 0, 0) ? "true" : "false") << std::endl;
    std::cout << "Test 5 (\"" << s5 << "\", \"" << p5 << "\"): "
              << (isMatchRecursive(s5, p5, 0, 0) ? "true" : "false") << std::endl;
    std::cout << "Test 6 (\"" << s6 << "\", \"" << p6 << "\"): "
              << (isMatchRecursive(s6, p6, 0, 0) ? "true" : "false") << std::endl;

    return 0;
}