C++ Online Compiler
Example: Wildcard Matching Recursive in C++
C
C++
C#
Java
Python
PHP
main.cpp
STDIN
Run
// 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; }
Output
Clear
ADVERTISEMENTS