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