# Regular Expression Matching Regular Expression Matching LeetCode Solution

Difficulty Level Hard

## Problem Statement

Regular Expression Matching Regular Expression Matching LeetCode Solution – Given an input string `s` and a pattern `p`, implement regular expression matching with support for `'.'` and `'*'` where:

• `'.'` Matches any single character.​​​​
• `'*'` Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial). s = “aa”

p = “a”

false

s = “aa”

p = “a*”

true

s = “ab”

p = “.*”

true

## Explanation:

i) “a” does not match the entire string “aa”.

ii) ‘*’ means zero or more of the preceding element, ‘a’. Therefore, by repeating ‘a’ once, it becomes “aa”.

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

## Approach:

s=’aab’, p=’c*a*b’

c * a * b

0 1 2 3 4 5

0 y

a 1

a 2

b 3

dp[i][j] denotes if s.substring(0,i) is valid for pattern p.substring(0,j). For example dp == true (denoted by y in the matrix) because when s and p are both empty they match. So if we somehow base dp[i+1][j+1] on previos dp[i][j]’s then the result will be dp[s.length()][p.length()].

So what about the first column? for an empty pattern p=””, the only thing that is valid is an empty string s=””, and that is already our dp which is true. That means rest of `dp[i]’ is false.

s=’aab’, p=’c*a*b’

c * a * b

0 1 2 3 4 5

0 y

a 1 n

a 2 n

b 3 n

What about the first row? In other words which pattern p matches empty string s=””? The answer is either an empty pattern p=””, or a pattern that can represent an empty string such as p=”a*”, p=”z*” or more interestingly a combination of them as in p=”a*b*c*”. Below for loop is used to populate dp[j]. Note how it uses previous states by checking dp[j-2].

for (int j=2; j<=p.length(); j++) {

dp[j] = p.charAt(j-1) == ‘*’ && dp[j-2];

}

At this stage our matrix has become as follows: Notice dp and dp are both true because p=”c*” and p=”c*a*” can both match an empty string.

s=’aab’, p=’c*a*b’

c * a * b

0 1 2 3 4 5

0 y n y n y n

a 1 n

a 2 n

b 3 n

So now we can start our main iteration. It is basically the same, we will iterate all possible s lengths (i) for all possible p lengths (j) and we will try to find a relationship based on previous results. Turns out there are two cases.

1. (p.charAt(j-1) == s.charAt(i-1) || p.charAt(j-1) == ‘.’) if the current characters match or pattern has . then the result is determined by the previous state dp[i][j] = dp[i-1][j-1]. Don’t be confused by the charAt(j-1) charAt(i-1) indexes using a -1 offset that is because our dp array is actually one index bigger than our string and pattern lenghts to hold the initial state dp
2. if p.charAt(j-1) == ‘*’ then either it acts as an empty set and the result is dp[i][j] = dp[i][j-2] or (s.charAt(i-1) == p.charAt(j-2) || p.charAt(j-2) == ‘.’) current char of string equals the char preceding * in pattern so the result is dp[i-1][j].

So here is the final state of the matrix after we evaluate all elements:

s=’aab’, p=’c*a*b’

c * a * b

0 1 2 3 4 5

0 y n y n y n

a 1 n n n y y n

a 2 n n n n y n

b 3 n n n n n y

## Code for Regular Expression Matching Regular Expression Matching

### Java Program

```class Solution {
public boolean isMatch(String s, String p) {
if (p == null || p.length() == 0) return (s == null || s.length() == 0);

boolean dp[][] = new boolean[s.length()+1][p.length()+1];
dp = true;
for (int j=2; j<=p.length(); j++) {
dp[j] = p.charAt(j-1) == '*' && dp[j-2];
}

for (int j=1; j<=p.length(); j++) {
for (int i=1; i<=s.length(); i++) {
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] || ((s.charAt(i-1) == p.charAt(j-2) || p.charAt(j-2) == '.') && dp[i-1][j]);
}
}
return dp[s.length()][p.length()];
}
}```

### C++ Program

```class Solution {
public:
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 = true;
for (int i = 0; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (p[j - 1] == '*') {
dp[i][j] = dp[i][j - 2] || (i && dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'));
} else {
dp[i][j] = i && dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
}
}
}
return dp[m][n];
}
};```

## Complexity Analysis for Regular Expression Matching Regular Expression Matching LeetCode Solution

Time Complexity: O(p.length() * s.length()).

Space Complexity: O(p.length() * s.length()).

Translate »