Algorithm
Problem Name: 10. Regular Expression Matching
Problem Link: https://leetcode.com/problems/regular-expression-matching/
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.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#define NOT_MATCH(A, B) (((B) == '.' && (A) == 0) || ((B) != '.' && (A) != (B)))
#define MATCH(A, B) ((A) == (B) || (B) == '.')
#define IDX(I, J) (((I) + 1) * (plen + 1) + (J) + 1)
bool match_recursive(char *s, char *p, int *retry) {
if (*p == 0) return *s == 0;
if (*(p + 1) == '*') {
while (*retry) {
if (match_recursive(s, p + 2, retry)) {
return true;
}
if (NOT_MATCH(*s, *p)) {
return false;
}
s ++;
}
*retry = 0;
return false;
}
if (NOT_MATCH(*s, *p)) {
return false;
}
return match_recursive(s + 1, p + 1, retry);
}
bool isMatch(char* s, char* p) {
#if 0 // 22ms
int retry = 1;
#else // 9ms
int *dp;
int i, j;
int slen, plen;
slen = strlen(s);
plen = strlen(p);
dp = calloc((slen + 1) * (plen + 1), sizeof(int));
dp[0] = 1;
for (j = 0; j < plen; j ++) {
if (p[j] == '*') {
dp[IDX(-1, j)] = dp[IDX(-1, j - 2)];
}
}
for (i = 0; i < slen; i++) {
for (j = 0; j < plen; j++) {
if (p[j] != '*') {
dp[IDX(i, j)] = dp[IDX(i - 1, j - 1)] && MATCH(s[i], p[j]);
} else {
dp[IDX(i, j)] = dp[IDX(i, j - 2)] || // no s
dp[IDX(i, j - 1)] || // one s
(MATCH(s[i], p[j - 1]) && dp[IDX(i - 1, j)]); // more s
}
}
}
i = dp[IDX(slen - 1, plen - 1)];
free(dp);
return i;
#endif
}
Input
s = "aa", p = "a"
Output
false
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
bool isMatch(string s, string p) {
if(p.empty()) return s.empty();
if(s.empty()) return p.empty() || (p[1] == '*' ? isMatch(s, p.substr(2)) : false);
if(p[0] != '.' && s[0] != p[0]) return p[1] == '*' ? isMatch(s, p.substr(2)) : false;
if(p[1] == '*') return isMatch(s.substr(1), p) || isMatch(s, p.substr(2));
return isMatch(s.substr(1), p.substr(1));
}
};
Input
s = "aa", p = "a*"
Output
true
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const isMatch = function(s, p) {
let memory = new Array(s.length + 1)
.fill(0)
.map(e => new Array(p.length + 1).fill(-1));
return memorySearch(s, 0, p, 0, memory);
};
const memorySearch = (s, i, p, k, memory) => {
if (memory[i][k] != -1) return memory[i][k];
if (k == p.length) return i == s.length;
let firstMatch = i < s.length && (s[i] == p[k] || p[k] == ".");
if (k + 1 < p.length && p[k + 1] == "*") {
memory[i][k] =
(firstMatch && memorySearch(s, i + 1, p, k, memory)) ||
memorySearch(s, i, p, k + 2, memory);
} else {
memory[i][k] = firstMatch && memorySearch(s, i + 1, p, k + 1, memory);
}
return memory[i][k];
};
Input
s = "ab", p = ".*"
Output
true
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def isMatch(self, s, p):
return bool(re.match(r"%s" %p, s)) and re.match(r"%s" %p, s).group(0) == s
Input
s = "aa", p = "a"
Output
false
#5 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _010_RegularExpressionMatching
{
public bool IsMatch(string s, string p)
{
var dp = new bool[s.Length + 1, p.Length + 1];
dp[s.Length, p.Length] = true;
for (var i = s.Length; i >= 0; i--)
for (var j = p.Length - 1; j >= 0; j--)
{
var match = i < s.Length && (s[i] == p[j] || p[j] == '.');
if (j + 1 < p.Length && p[j + 1] == '*')
dp[i, j] = dp[i, j + 2] || (match && dp[i + 1, j]);
else
dp[i, j] = match && dp[i + 1, j + 1];
}
return dp[0, 0];
}
}
}
Input
s = "aa", p = "a*"
Output
true