In the **Regular Expression Matching** problem we have given two strings one (let’s assume it **x**) consists of only lower case alphabets and second (let’s assume it **y**) consists of lower case alphabets with two special characters i.e, “.” and “*”. The task is to find whether the second string matches the first string or not. If it matches then print **“true” **otherwise print **“false”**.

The two characters used here means:

“.” – pattern matches any single character i.e, “.” can be replaced with any character required to match the first string

“*” – pattern matches 0 or more occurrence of character before “*” i.e, “*” can be replaced by any the preceding character zero or more times as required to match the first string

Note:

- x could be empty or can contain only lowercase letters.
- y could also be empty or can contain only lowercase letters or only characters like “.” or “*” or both (i.e., lowercase letters and characters like “.” and “*”)

Table of Contents

## Example

**Input**

x = “aa”

y = “a”

**Output**

false

**Explanation**

As y does not match the entire string i.e., “a” (y) does not match the string “aa” (x).

**Input**

x = “aa”

y = “a*”

**Output**

true

**Explanation**

As “*” means repetition of the preceding letter zero or more times and removing the special character. So by repeating “a” ones in the string “a*” it will become “aa” and both the string will become the same.

**Input**

x = “acb”

y = “a.b”

**Output**

true

**Explanation**

Here we can replace “.” by any character so replacing “.” in “a.b” by “c” we will get our desired string i.e., acb, and both the string will become true.

**Input**

x = “ab”

y = “.*”

**Output**

true

**Explanation**

“.*” means “zero or more (*) of any character (.)”.

## Algorithm

There are many solutions to this problem but the most efficient way is to solve it using dynamic programming.

- Get the length of both
**“x”**and**“y”**in some variable say**“m”**and**“n”**respectively. - check if
**“m”**equals to**“0”**then return print**false**. - Initialize a 2d array(say dp) with the length of
**“x”**as row and**“y”**as the column. - Mark the array as false.
- Initialize
**“0,0”**index of array as**true** - Run a for loop till
**“m”**from 1- Inside for loop check, if y[i-1] == ‘*’
- If yes then dp[0][i] = dp[0][j-1]

- Inside for loop check, if y[i-1] == ‘*’
- Initialise a nested for loop: One with 1 up to
**“m”**and second with 1 to**“n”**- In for loop check, if y[j-1] == ‘*’
- if yes then dp[i][j] = dp[i][j – 1] || dp[i – 1][j]

- else check if y[j – 1] == ‘.’ || x[i – 1] == y[j – 1]
- if yes then dp[i][j] = dp[i – 1][j – 1]

- else mark dp[i][j] as false i.e., dp[i][j] == false

- In for loop check, if y[j-1] == ‘*’
- Print the result of dp[n][m] i.e., last index of dp

## Implementation in C++ for Regular Expression Matching

#include <bits/stdc++.h> using namespace std; bool isMatch(char x[], char y[]) { int n = strlen(x); int m = strlen(y); if (m == 0) return (n == 0); bool dp[n + 1][m + 1]; memset(dp, false, sizeof(dp)); dp[0][0] = true; for (int i = 1; i <= m; i++) { if (y[i - 1] == '*') { dp[0][i] = dp[0][i - 1]; } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (y[j - 1] == '*') { dp[i][j] = dp[i][j - 1] || dp[i - 1][j]; } else if (y[j - 1] == '.' || x[i - 1] == y[j - 1]) { dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = false; } } } return dp[n][m]; } int main() { char x[] = "acb"; char y[] = "a.b"; cout<< boolalpha<<(isMatch(x, y)); return 0; }

true

## Implementation in Java for Regular Expression Matching

import java.util.Arrays; public class solution { static boolean isMatch(String x, String y) { int n = x.length(); int m = y.length(); if (m == 0) return (n == 0); boolean[][] dp = new boolean[n + 1][m + 1]; for (int i = 0; i<n + 1; i++) { Arrays.fill(dp[i], false); } dp[0][0] = true; for (int j = 1; j<= m; j++) { if (y.charAt(j - 1) == '*') { dp[0][j] = dp[0][j - 1]; } } for (int i = 1; i<= n; i++) { for (int j = 1; j<= m; j++) { if (y.charAt(j - 1) == '*') { dp[i][j] = dp[i][j - 1] || dp[i - 1][j]; } else if (y.charAt(j - 1) == '.' || x.charAt(i - 1) == y.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = false; } } } return dp[n][m]; } public static void main(String args[]) { String x = "acb"; String y = "a.b"; System.out.println((isMatch(x, y))); } }

true

## Complexity Analysis for Regular Expression Matching

### Time Complexity

O(m×n) where **m** is the length of **“x”** and **n** is the length of **“y”**

### Space Complexity

O(m×n) where **m** is the length of **“x”** and **n** is the length of **“y”**