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:
scould be empty and contains only lowercase lettersa-z.pcould be empty and contains only lowercase lettersa-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];
}
};