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 <= 201 <= p.length <= 30scontains only lowercase English letters.pcontains 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[0][0] = 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[0][j - 1])
dp[0][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[0][0] = true;
for (int j = 0; j < p.length(); ++j)
if (p.charAt(j) == '*' && dp[0][j - 1])
dp[0][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[0][0] = 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[0][j - 1]:
dp[0][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]
