## Algorithm

Problem Name: 10. 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 <= 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.

## 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
}
``````
Copy The Code &

Input

cmd
s = "aa", p = "a"

Output

cmd
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));
}
};
``````
Copy The Code &

Input

cmd
s = "aa", p = "a*"

Output

cmd
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];
};
``````
Copy The Code &

Input

cmd
s = "ab", p = ".*"

Output

cmd
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
``````
Copy The Code &

Input

cmd
s = "aa", p = "a"

Output

cmd
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];
}
}
}
``````
Copy The Code &

Input

cmd
s = "aa", p = "a*"

Output

cmd
true