fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. using namespace std;
  5.  
  6. bool isMatch(string s, string p) {
  7.     int m = s.length(), n = p.length();
  8.     vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
  9.  
  10.     // Base case: both strings are empty
  11.     dp[0][0] = true;
  12.  
  13.     // Initialize dp for patterns with '*' that can match an empty string
  14.     for (int j = 2; j <= n; j++) {
  15.         if (p[j - 1] == '*') {
  16.             dp[0][j] = dp[0][j - 2];
  17.         }
  18.     }
  19.  
  20.     // Fill the dp table
  21.     for (int i = 1; i <= m; i++) {
  22.         for (int j = 1; j <= n; j++) {
  23.             if (p[j - 1] == '.' || p[j - 1] == s[i - 1]) {
  24.                 // Current characters match or pattern has '.'
  25.                 dp[i][j] = dp[i - 1][j - 1];
  26.             } else if (p[j - 1] == '*') {
  27.                 // Handle '*'
  28.                 dp[i][j] = dp[i][j - 2]; 
  29.                 // Treat '*' as matching zero of the preceding character
  30.                 if (p[j - 2] == '.' || p[j - 2] == s[i - 1]) {
  31.                     dp[i][j] = dp[i][j] || dp[i - 1][j]; 
  32.                     // Match one or more of the preceding character
  33.                 }
  34.             }
  35.         }
  36.     }
  37.  
  38.     return dp[m][n];
  39. }
  40.  
  41. int main() {
  42.     string s;
  43.     string p;
  44.  
  45. 	cin >> s >> p;
  46.  
  47.     cout << boolalpha << isMatch(s, p) << endl; 
  48.  
  49.     return 0;
  50. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
aab
c*a*b
stdout
copy 
true
https://ideone.com/4wIE68
language:
C++14 (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!