In this guide we will provide 10. Regular Expression Matching LeetCode Solution with best time and space complexity. The solution to Regular Expression Matching problem is provided in various programming languages like C++, Java and python. This will be helpful for you if you are preparing for placements, hackathon, interviews or practice purposes. The solutions provided here are very easy to follow and with detailed explanations.
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 <= 20
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.
Complexity Analysis
Time Complexity: O(mn)
Space Complexity: O(mn)
10. Regular Expression Matching LeetCode 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] == '*') {
// The minimum index of '*' is 1.
const bool noRepeat = dp[i + 1][j - 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];
}
}; /* code provided by PROGIEZ */
10. Regular Expression Matching LeetCode 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) == '*') {
// The minimum index of '*' is 1.
final boolean noRepeat = dp[i + 1][j - 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);
}
} // code provided by PROGIEZ
10. Regular Expression Matching LeetCode 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] == '*':
# The minimum index of '*' is 1.
noRepeat = dp[i + 1][j - 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] #code by PROGIEZ
