# Regular Expression Matching 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 = 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];
}
};