Regular Expression Matching In C,CPP,JAVA,PYTHON,C#,JS

/ DSA / By
Spread the love
Close-up of a computer screen displaying programming code in a dark environment.

Problem Statement:

Given a string s and a pattern p, implement a regular expression matching algorithm to determine if s matches p. The pattern may include the characters:

  • ‘.’ (dot), which matches any single character.
  • ‘*’ (star), which matches zero or more of the preceding element.

The matching should cover the entire string (not just a substring).

Example:

Input:

  • s = "aa"
  • p = "a*"

Output:

  • True

Explanation: The pattern a* matches zero or more a‘s. In this case, the pattern a* matches the string "aa".

Input:

  • s = "mississippi"
  • p = "mis*is*p*."

Output:

  • False

Explanation: The pattern doesn’t match the string.

Approach:

This problem can be efficiently solved using Dynamic Programming (DP). The idea is to build a 2D DP table where each entry dp[i][j] represents whether the substring s[0..i-1] matches the pattern p[0..j-1].

  1. Base Case Initialization:
    • dp[0][0] = true because an empty string matches an empty pattern.
    • For any i > 0, dp[i][0] = false because a non-empty string cannot match an empty pattern.
    • For any j > 0, dp[0][j] is true only if the pattern p[0..j-1] can match an empty string. This happens when the pattern has multiple * that can match zero characters (e.g., a*, .*).
  2. DP Transition:
    • If p[j-1] is a letter (not . or *):
      • dp[i][j] = dp[i-1][j-1] if s[i-1] == p[j-1] (or if p[j-1] == '.').
    • If p[j-1] is *:
      • There are two possibilities:
        1. We don’t use the * (i.e., match zero characters of the preceding character): dp[i][j] = dp[i][j-2].
        2. We use the * to match one or more characters: dp[i][j] = dp[i-1][j] if s[i-1] == p[j-2] or p[j-2] == '.'.

Time Complexity:

  • The time complexity is O(m * n), where m is the length of the string s and n is the length of the pattern p, because we are filling a DP table of size m+1 by n+1.

Space Complexity:

  • The space complexity is O(m * n) due to the 2D DP table.

Algorithm:

  1. Initialize a DP table dp of size (m+1) x (n+1), where m is the length of the string s and n is the length of the pattern p.
  2. Set the base cases in the DP table.
  3. Use a nested loop to fill the DP table according to the recurrence relation described.
  4. The result will be in dp[m][n].

Code Implementation:

1. C

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

bool isMatch(char* s, char* p) {
    int m = strlen(s), n = strlen(p);
    bool dp[m+1][n+1];

    dp[0][0] = true;
    for (int j = 1; j <= n; j++) {
        dp[0][j] = (p[j-1] == '*' && dp[0][j-2]);
    }

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (p[j-1] == s[i-1] || p[j-1] == '.') {
                dp[i][j] = dp[i-1][j-1];
            } else if (p[j-1] == '*') {
                dp[i][j] = dp[i][j-2] || ((s[i-1] == p[j-2] || p[j-2] == '.') && dp[i-1][j]);
            } else {
                dp[i][j] = false;
            }
        }
    }

    return dp[m][n];
}

int main() {
    char s[] = "aa";
    char p[] = "a*";
    printf("%s\n", isMatch(s, p) ? "True" : "False");
    return 0;
}

2. C++

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

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;

    for (int j = 1; j <= n; j++) {
        if (p[j-1] == '*') {
            dp[0][j] = dp[0][j-2];
        }
    }

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (p[j-1] == s[i-1] || p[j-1] == '.') {
                dp[i][j] = dp[i-1][j-1];
            } else if (p[j-1] == '*') {
                dp[i][j] = dp[i][j-2] || (dp[i-1][j] && (s[i-1] == p[j-2] || p[j-2] == '.'));
            }
        }
    }

    return dp[m][n];
}

int main() {
    string s = "aa";
    string p = "a*";
    cout << (isMatch(s, p) ? "True" : "False") << endl;
    return 0;
}

3. Java

public class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];

        dp[0][0] = true;

        for (int j = 1; j <= n; j++) {
            if (p.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 2];
            }
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p.charAt(j - 1) == s.charAt(i - 1) || p.charAt(j - 1) == '.') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.'));
                }
            }
        }

        return dp[m][n];
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.isMatch("aa", "a*"));  // Output: true
    }
}

4. Python

def isMatch(s: str, p: str) -> bool:
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]

    dp[0][0] = True
    for j in range(1, n + 1):
        if p[j - 1] == '*':
            dp[0][j] = dp[0][j - 2]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j - 1] == s[i - 1] or p[j - 1] == '.':
                dp[i][j] = dp[i - 1][j - 1]
            elif p[j - 1] == '*':
                dp[i][j] = dp[i][j - 2] or (dp[i - 1][j] and (s[i - 1] == p[j - 2] or p[j - 2] == '.'))

    return dp[m][n]

# Test the function
print(isMatch("aa", "a*"))  # Output: True

5. C#

using System;

public class Solution {
    public bool IsMatch(string s, string p) {
        int m = s.Length, n = p.Length;
        bool[,] dp = new bool[m + 1, n + 1];

        dp[0, 0] = true;

        for (int j = 1; j <= n; j++) {
            if (p[j - 1] == '*') {
                dp[0, j] = dp[0, j - 2];
            }
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p[j - 1] == s[i - 1] || p[j - 1] == '.') {
                    dp[i, j] = dp[i - 1, j - 1];
                } else if (p[j - 1] == '*') {
                    dp[i, j] = dp[i, j - 2] || (dp[i - 1, j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'));
                }
            }
        }

        return dp[m, n];
    }

    public static void Main() {
        Solution solution = new Solution();
        Console.WriteLine(solution.IsMatch("aa", "a*"));  // Output: True
    }
}

6. JavaScript

var isMatch = function(s, p) {
    const m = s.length, n = p.length;
    const dp = Array.from(Array(m + 1), () => Array(n + 1).fill(false));

    dp[0][0] = true;

    for (let j = 1; j <= n; j++) {
        if (p[j - 1] === '*') {
            dp[0][j] = dp[0][j - 2];
        }
    }

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (p[j - 1] === s[i - 1] || p[j - 1] === '.') {
                dp[i][j] = dp[i - 1][j - 1];
            } else if (p[j - 1] === '*') {
                dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && (s[i - 1] === p[j - 2] || p[j - 2] === '.'));
            }
        }
    }

    return dp[m][n];
};

// Test the function
console.log(isMatch("aa", "a*"));  // Output: true

Conclusion:

This algorithm efficiently solves the problem of regular expression matching using Dynamic Programming (DP). The DP approach ensures that we check all possible ways a substring of s can match the pattern p. The time and space complexities are O(m * n), where m and n are the lengths of the string and the pattern, respectively.