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: Regular Expression Matching

The task is to implement a function that matches a string with a given regular expression pattern. The pattern can include the following special characters:

  • .: Matches any single character.
  • *: Matches zero or more of the preceding element.

You need to implement a function that determines whether a given string matches the pattern.

Example:

Input:

  • String: "aa"
  • Pattern: "a*"

Output:

  • True (The string "aa" matches the pattern "a*", which means zero or more a characters.)

Input:

  • String: "mississippi"
  • Pattern: "mis*is*p*."

Output:

  • False (The string "mississippi" does not match the pattern "mis*is*p*.")

Approach:

1. Dynamic Programming Approach:

We can use a dynamic programming (DP) approach to solve the problem efficiently.

Steps:

  1. DP Table Setup:
    Define a 2D DP table where dp[i][j] indicates whether the first i characters of the string match the first j characters of the pattern.
  2. Base Case:
    • dp[0][0] is True because an empty pattern matches an empty string.
    • For the pattern containing *, handle cases where * represents repeating characters (zero occurrences).
  3. Fill the DP Table:
    Iterate over the string and the pattern to fill the DP table:
    • If pattern[j-1] is a regular character or ., check if the current string character matches the pattern.
    • If pattern[j-1] is *, check the two cases: zero or more occurrences of the preceding character.
  4. Final Answer:
    The answer is in dp[m][n], where m is the length of the string and n is the length of the pattern.

2. Time Complexity:

  • Time Complexity: O(m×n)O(m \times n)O(m×n), where m is the length of the string and n is the length of the pattern.
  • Space Complexity: O(m×n)O(m \times n)O(m×n) for the DP table.

Code Implementation

C Code:

#include <stdio.h>
#include <string.h>
#include <stdbool.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] || ((p[j-2] == s[i-1] || p[j-2] == '.') && dp[i-1][j]);
            } else {
                dp[i][j] = false;
            }
        }
    }
    return dp[m][n];
}

int main() {
    char s[] = "aa";
    char p[] = "a*";
    if (isMatch(s, p)) {
        printf("Match\n");
    } else {
        printf("No Match\n");
    }
    return 0;
}

C++ Code:

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

bool isMatch(string s, string p) {
    int m = s.length(), n = p.length();
    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] || (p[j-2] == s[i-1] || p[j-2] == '.') && dp[i-1][j];
            } else {
                dp[i][j] = false;
            }
        }
    }
    return dp[m][n];
}

int main() {
    string s = "aa";
    string p = "a*";
    if (isMatch(s, p)) {
        cout << "Match" << endl;
    } else {
        cout << "No Match" << endl;
    }
    return 0;
}

Java Code:

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] || 
                        (p.charAt(j - 2) == s.charAt(i - 1) || p.charAt(j - 2) == '.') && dp[i - 1][j];
                } else {
                    dp[i][j] = false;
                }
            }
        }
        return dp[m][n];
    }

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

Python Code:

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 \
                           (p[j - 2] == s[i - 1] or p[j - 2] == '.') and dp[i - 1][j]
            else:
                dp[i][j] = False
    
    return dp[m][n]

# Example Usage
print(isMatch("aa", "a*"))  # Output: True

C# Code:

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] || 
                               (p[j - 2] == s[i - 1] || p[j - 2] == '.') && dp[i - 1, j];
                } else {
                    dp[i, j] = false;
                }
            }
        }
        return dp[m, n];
    }
    
    public static void Main() {
        Solution solution = new Solution();
        Console.WriteLine(solution.IsMatch("aa", "a*"));  // Output: True
    }
}

JavaScript Code:

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] || 
                           (p[j - 2] === s[i - 1] || p[j - 2] === '.') && dp[i - 1][j];
            }
        }
    }

    return dp[m][n];
};

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

Summary:

  • The dynamic programming approach solves the problem by building a DP table to represent subproblems, ensuring an optimal solution.
  • The time complexity is O(m×n)O(m \times n)O(m×n), where m is the length of the string and n is the length of the pattern.
  • Space complexity is also O(m×n)O(m \times n)O(m×n) due to the DP table.