Regular Expression Matching - CPP Solution

1. Introduction

This blog post discusses an intriguing problem in string processing and pattern matching: implementing a regular expression matcher in C++. The matcher should support two special characters: '.' which matches any single character, and '*' which matches zero or more of the preceding element. This problem is a good example of dynamic programming and recursion in C++.

Problem

Given an input string 's' and a pattern 'p', implement a regular expression matching function. The function should support two special characters:

- '.' Matches any single character.

- '*' Matches zero or more of the preceding element.

The goal is to check if the pattern matches the entire input string, not just a part of it.

2. Solution Steps

1. Use recursion to match the pattern with the string.

2. Handle the cases when pattern contains the special characters '.' and '*'.

3. Implement base cases for when the string and pattern are empty.

4. Use dynamic programming to optimize the solution by storing intermediate results.

3. Code Program

#include <iostream>
#include <vector>
using namespace std;

// Function to implement regular expression matching
bool isMatch(string s, string p) {
    int m = s.size(), n = p.size();
    vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
    dp[0][0] = true; // Base case: empty string and empty pattern are a match

    // Handle patterns formed by '*' characters
    for (int i = 1; i <= n; i++) {
        if (p[i - 1] == '*') {
            dp[0][i] = dp[0][i - 2];
        }
    }

    // Iterate through string and pattern
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (p[j - 1] == '.' || p[j - 1] == s[i - 1]) {
                // Match single character
                dp[i][j] = dp[i - 1][j - 1];
            } else if (p[j - 1] == '*') {
                // '*' matches zero or more of the preceding element
                dp[i][j] = dp[i][j - 2] || (p[j - 2] == s[i - 1] || p[j - 2] == '.') && dp[i - 1][j];
            }
        }
    }
    return dp[m][n]; // Return final result
}

int main() {
    string s = "aab";
    string p = "c*a*b";
    cout << "Match result: " << isMatch(s, p) << endl;
    return 0;
}

Output:

Match result: 1

Explanation:

1. The input string "aab" and the pattern "c*a*b" are processed.

2. The pattern includes '*' characters which match zero or more of the preceding element.

3. The dynamic programming approach is used to store and utilize previous match results.

4. The final result is true (represented as 1), indicating that the pattern matches the entire string.

5. The function correctly handles the special characters '.' and '*', demonstrating its capability to perform complex regular expression matching.