# Regular Expression Matching Program Solution

Problem Statement: Regular Expression Matching Program Solution | Leetcode Program Solution

We at gradjobopenings.com provide free job alerts of freshers job drives. In this website we list on campus job openings for freshers and off campus job openings for freshers and also work from home job openings. This is the best website to apply for off campus drive in India. Visit our website for government job alerts and private job alerts. We also list free interview notes and study materials, one of the best interview study website.comfortable to face the interviews:

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.
• Time: O(mn)O(mn)
• Space: O(mn)O(mn)

### Regular Expression Matching Program Solution in C++

``````class Solution {
public:
bool isMatch(string s, string p) {
const int m = s.length();
const int n = p.length();
// dp[i][j] := true if s[0..i) matches p[0..j)
vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
dp = true;

auto isMatch = [&](int i, int j) -> bool {
return j >= 0 && p[j] == '.' || s[i] == p[j];
};

for (int j = 0; j < p.length(); ++j)
if (p[j] == '*' && dp[j - 1])
dp[j + 1] = true;

for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (p[j] == '*') {
const bool noRepeat = dp[i + 1][j - 1];  // min index of '*' is 1
const bool doRepeat = isMatch(i, j - 1) && dp[i][j + 1];
dp[i + 1][j + 1] = noRepeat || doRepeat;
} else if (isMatch(i, j)) {
dp[i + 1][j + 1] = dp[i][j];
}

return dp[m][n];
}
};
``````

### Regular Expression Matching Program Solution in JAVA

``````class Solution {
public boolean isMatch(String s, String p) {
final int m = s.length();
final int n = p.length();
// dp[i][j] := true if s[0..i) matches p[0..j)
boolean[][] dp = new boolean[m + 1][n + 1];
dp = true;

for (int j = 0; j < p.length(); ++j)
if (p.charAt(j) == '*' && dp[j - 1])
dp[j + 1] = true;

for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (p.charAt(j) == '*') {
final boolean noRepeat = dp[i + 1][j - 1]; // min index of '*' is 1
final boolean doRepeat = isMatch(s, i, p, j - 1) && dp[i][j + 1];
dp[i + 1][j + 1] = noRepeat || doRepeat;
} else if (isMatch(s, i, p, j)) {
dp[i + 1][j + 1] = dp[i][j];
}

return dp[m][n];
}

private boolean isMatch(final String s, int i, final String p, int j) {
return j >= 0 && p.charAt(j) == '.' || s.charAt(i) == p.charAt(j);
}
}
``````

### Regular Expression Matching Program Solution in PYTHON

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

def isMatch(i: int, j: int) -> bool:
return j >= 0 and p[j] == '.' or s[i] == p[j]

for j, c in enumerate(p):
if c == '*' and dp[j - 1]:
dp[j + 1] = True

for i in range(m):
for j in range(n):
if p[j] == '*':
noRepeat = dp[i + 1][j - 1]  # min index of '*' is 1
doRepeat = isMatch(i, j - 1) and dp[i][j + 1]
dp[i + 1][j + 1] = noRepeat or doRepeat
elif isMatch(i, j):
dp[i + 1][j + 1] = dp[i][j]

return dp[m][n]
``````
error: Content is protected !!