Given an input string (`s`

) and a pattern (`p`

), implement regular expression matching with support for `'.'`

and `'*'`

.

```
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
```

The matching should cover the **entire** input string (not partial).

**Note:**

`s`

could be empty and contains only lowercase letters`a-z`

.`p`

could be empty and contains only lowercase letters`a-z`

, and characters like`.`

or`*`

.

**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 (.)".
```

**Example 4:**

```
Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".
```

**Example 5:**

```
Input:
s = "mississippi"
p = "mis*is*p*."
Output: false
```

**Solution:**

DP. 4 cases when D(i,j) is true:

1) D(i-1,j-1) and a(i-1) matches b(j-1); Ex: “aa” and “aa”

2) D(i,j-1) and b(j-1) is *; Ex: “aaa” and “aa*”

3) D(i-1,j) and b(j-1) is * and a(i-1) matches b(j-2); Ex: “aaa” and “a*”;

4) D(i, j-2) and b(j-1) is *; Ex: “a” amd “ac*”;

Add space before each string to avoid indexing error.

```
class Solution {
public:
bool isMatch(string a, string b) {
a = ' '+a;
b = ' '+b;
int n = a.size();
int m = b.size();
vector<vector<int> > D(n+1, vector<int>(m+1, 0));
D[0][0] = 1;
for(int j = 1; j <= m; j++){
for(int i = 1; i <= n; i++){
if(D[i-1][j-1] && (a[i-1]==b[j-1] || b[j-1]=='.')){
D[i][j] = 1;
continue;
}
if(D[i][j-1] && b[j-1] == '*'){
D[i][j] = 1;
continue;
}
if(j>1 && D[i-1][j] && (a[i-1] == b[j-2] || b[j-2] == '.') && b[j-1] == '*' ){
D[i][j] = 1;
continue;
}
if(j>1 && D[i][j-2] && b[j-1] == '*'){
D[i][j] = 1;
continue;
}
}
}
return D[n][m];
}
};
```