Regular Expression Matching Leetcode Solution

In this post, we are going to solve the Regular Expression Matching Leetcode Solution problem of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.

Problem

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).

Example 1:

```Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
```

Example 2:

```Input: s = "aa", p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
```

Example 3:

```Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".
```

Constraints:

• `1 <= s.length <= 20`
• `1 <= p.length <= 30`
• `s` contains only lowercase English letters.
• `p` contains only lowercase English letters, `'.'`, and `'*'`.
• It is guaranteed for each appearance of the character `'*'`, there will be a previous valid character to match.

Now, lets see the leetcode solution of Regular Expression Matching Leetcode Solution.

Regular Expression Matching Leetcode Solutionin Python

```class Solution:
def isMatch(self, s: str, p: str) -> bool:
s, p = ' '+ s, ' '+ p
lenS, lenP = len(s), len(p)
dp = [[0]*(lenP) for i in range(lenS)]
dp[0][0] = 1

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

for i in range(1, lenS):
for j in range(1, lenP):
if p[j] in {s[i], '.'}:
dp[i][j] = dp[i-1][j-1]
elif p[j] == "*":
dp[i][j] = dp[i][j-2] or int(dp[i-1][j] and p[j-1] in {s[i], '.'})

return bool(dp[-1][-1])```

Regular Expression Matching Leetcode Solutionin CPP

```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[0][0] = 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];
}
};```

Regular Expression Matching Leetcode Solution in Java

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

Note: This problem Regular Expression Matching is generated by Leetcode but the solution is provided by Chase2learn This tutorial is only for Educational and Learning purposes.

Sharing Is Caring