Solution For Regular Expression Matching

Problem Statement

Given an input string (s) and a pattern (p), implement regular expression matching with support for ‘.’ and ‘*’.

‘.’ Matches any single character.

‘*’ Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

Note:

s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like . or *.

Example 1:
Input: s = “aa”, p = “a”
Output: false
Explanation: “a” does not match the entire string “aa”.

Example 2:
Input: s = “aab”, p = “cab”
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, “cab” matches “aab”.

Solution

To solve this problem, we can use a dynamic programming approach. We can create a two-dimensional boolean array dp, where dp[i][j] represents whether the substring of s from 0 to i-1 can be matched with the substring of p from 0 to j-1.

Here are the steps to fill out the dp array:

1. Initialize dp[0][0] as true since an empty string can match another empty string.
2. Fill in the first row dp[0][j] according to the pattern. If p[j-1] is ‘‘, then dp[0][j] is equal to dp[0][j-2] (because ”” means zero or more of the preceding element).
3. Fill in the first column dp[i][0] as false since a non-empty string cannot match an empty pattern.
4. For each dp[i][j], if s[i-1] == p[j-1] or p[j-1] == ‘.’, we can match the characters. Therefore, dp[i][j] is equal to dp[i-1][j-1].
5. If p[j-1] == ‘‘, there are two cases to consider:
a) if p[j-2] == s[i-1] or p[j-2] == ‘.’, the ‘
‘ can either match zero or more characters. Therefore, we need to check dp[i][j-2] (zero match) or dp[i-1][j] (one or more matches)
b) if p[j-2] != s[i-1], the ‘*’ can only match zero characters. Therefore, dp[i][j] is equal to dp[i][j-2]

Finally, we return dp[m][n], where m and n are the lengths of s and p respectively.

Here is the Python code for the solution:

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

``````    # Fill in the first row dp[0][j]
for j in range(2, n + 1):
if p[j-1] == '*':
dp[0][j] = dp[0][j-2]

# Fill in the first column dp[i][0]

# Fill in the rest of the dp array
for i in range(1, m + 1):
for j in range(1, n + 1):
if s[i-1] == p[j-1] or p[j-1] == '.':
dp[i][j] = dp[i-1][j-1]
elif p[j-1] == '*':
if p[j-2] == s[i-1] or p[j-2] == '.':
dp[i][j] = dp[i][j-2] or dp[i-1][j]
else:
dp[i][j] = dp[i][j-2]

return dp[m][n]
``````

Time Complexity: O(mn), where m and n are the lengths of s and p respectively.
Space Complexity: O(m
n), the size of the dp array.

Step by Step Implementation For Regular Expression Matching

```public class Solution {
public boolean isMatch(String s, String p) {
// base case
if (p.isEmpty()) return s.isEmpty();

// special case
if (p.length() == 1) {

// if the length of s is 0, return false
if (s.length() < 1) return false;

//if the first does not match, return false
else if ((p.charAt(0) != s.charAt(0)) && (p.charAt(0) != '.')) return false;

// otherwise, compare the rest of the string of s and p.
else return isMatch(s.substring(1), p.substring(1));
}

// case 1: when the second char of p is not '*'
if (p.charAt(1) != '*') {

if (s.isEmpty()) return false;
if ((p.charAt(0) != s.charAt(0)) && (p.charAt(0) != '.')) return false;
else return isMatch(s.substring(1), p.substring(1));
}

// case 2: when the second char of p is '*', complex case.
else {
//case 2.1: a char & '*' can stand for 0 element
if (isMatch(s, p.substring(2))) return true;

//case 2.2: a char & '*' can stand for 1 or more preceding element,
//so try every sub string
int i = 0;
while (i < s.length() && (s.charAt(i) == p.charAt(0) || p.charAt(0) == '.')) {
if (isMatch(s.substring(i + 1), p.substring(2))) return true;
i++;
}
return false;
}
}
}```
```def isMatch(s, p):

# Base Case 1: if both are empty
if not s and not p:
return True

# Base Case 2: if one is empty
if not s or not p:
return False

# match first characters and recur for the remaining
if s[0] == p[0] or p[0] == '.':
return isMatch(s[1:], p[1:])

# If p's first character is '*', two cases arise:
# a) We consider the case where '*' matches with no character in s.
#    In this case, we recur for p[2:]
# b) '*' matches one or more characters in s
if p[0]=='*':
return isMatch(s, p[2:]) or isMatch(s[1:], p)

# If characters don't match
return False```
```var isMatch = function(s, p) {
};```
```class Solution {
public:
bool isMatch(string s, string p) {

// Base case
if (p.empty()) return s.empty();

// Special case
if (p.size() == 1) {
return (s.size() == 1 && (s[0] == p[0] || p[0] == '.'));
}

// If the second character is not '*'
if (p[1] != '*') {
if (s.empty()) return false;
return (s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), p.substr(1));
}

// If the second character is '*', complex case.
while (!s.empty() && (s[0] == p[0] || p[0] == '.')) {
if (isMatch(s, p.substr(2))) return true;
s = s.substr(1);
}

// If there is a '*', we can ignore it and the character before it.
return isMatch(s, p.substr(2));
}
};```
```public class Solution {
public bool IsMatch(string s, string p) {
// base case
if (p.Length == 0) return s.Length == 0;

// special case
if (p.Length == 1) {

// if the length of s is 0, return false
if (s.Length == 0) {
return false;
}

//if the first does not match, return false
else if ((p[0] != s[0]) && (p[0] != '.')) {
return false;
}

// otherwise, compare the rest of the string of s and p.
else {
return IsMatch(s.Substring(1), p.Substring(1));
}
}

// case 1: when the second char of p is not '*'
if (p[1] != '*') {
if (s.Length == 0) {
return false;
}
if ((p[0] != s[0]) && (p[0] != '.')) {
return false;
}
else {
return IsMatch(s.Substring(1), p.Substring(1));
}
}

// case 2: when the second char of p is '*', complex case.
else {
//case 2.1: a char & '*' can stand for 0 element
if (IsMatch(s, p.Substring(2))) {
return true;
}

//case 2.2: a char & '*' can stand for 1 or more preceding element,
//so try every sub string
int i = 0;
while (i```
Scroll to Top

Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]